Google’s coding interview question — Check if two strings are isomorphic

Problem Statement:

Given two strings ‘str1’ and ‘str2’, check if these two strings are isomorphic to each other.

Two strings str1 and str2 are called isomorphic if there is a one-to-one mapping possible for every character of str1 to every character of str2 while preserving the order.

Note: All occurrences of every character in str1 should map to the same character in str2.

Example 1:

Input:
str1 = aab
str2 = xxy
Output: 1
Explanation: There are two different
characters in aab and xxy, i.e a and b
with frequency 2 and 1 respectively.

Example 2:

Input:
str1 = aab
str2 = xyz
Output: 0
Explanation: There are two different
charactersin aab but there are three
different charactersin xyz. So there
won't be one to one mapping between
str1 and str2.

Expected Time Complexity: O(|str1|+|str2|).
Expected Auxiliary Space: O(Number of different characters).

Asked by — Google.

A. Brute Force Approach:

1. Traverse through the first string ‘str1’.
2. For each character in str1, check for the corresponding mapping of that character in str2.
3. Check whether the mapping is in the correct order.

Complexity Analysis:

Time Complexity: O(n²).
’n’ is the total number of characters in str1.

Auxiliary Space: O(Number of different characters).

B. Optimal Solution- Using Hashing

For this solution, we will first discuss the edge case.

The length of str1 is not equal to the length of str2. The strings are not isomorphic in such a case.

We can use a hashmap, where the characters of str1 are keys and characters of str2 are mapped as values, as there is a mapping of each character of str1 in str2.

We will insert the values for the corresponding key, keeping the following conditions in mind. Do not add values to the hashmap if:

1. Keys are same but the values are different.
2. Keys are different but the values are same.

Otherwise, we simply add to the hashmap the mapping of characters at ‘str1’ and ‘str2’.

Code:

Complexity Analysis:

Time Complexity: O(n)

Space complexity: O(Number of different characters)

If you liked this article, please click the “clap” button 👏 a few times.

Gives me enough motivation to put out more content like this. Please share it with a friend who you think this article might help.

Follow me Varsha Das to receive my weekly articles.

Connect with me — Varsha Das | LinkedIn

Follow my Youtube channel where we discuss Data Structures & Algorithms.

Thanks for reading.

Happy learning! 😁