Isomorphic Strings

Isomorphic Strings

1. What is this problem about?

The Isomorphic Strings interview question asks you to determine if two strings, s and t, are isomorphic. Two strings are isomorphic if the characters in s can be replaced to get t. The rules are:

• All occurrences of a character must be replaced with another character while preserving the order of characters.
• No two characters may map to the same character, but a character may map to itself.

2. Why is this asked in interviews?

This is a popular question at companies like Apple, Amazon, and Uber. It tests your proficiency with Hash Table interview patterns and your ability to maintain a one-to-one mapping (bijective mapping). It evaluations whether you can identify that a single map is often not enough to ensure that two different characters in s don't map to the same character in t.

3. Algorithmic pattern used

This problem follows the Character Mapping (Dual-Map or Position tracking) pattern.

1. Two Maps: Use two hash maps (or arrays of size 256): one for s -> t and one for t -> s.
2. Iterate: Traverse both strings simultaneously.
3. Consistency Check: For each pair $(c1, c2)$:
   • If $c1$ was already mapped to something other than $c2$, return false.
   • If $c2$ was already mapped to something other than $c1$, return false.
   • Otherwise, record the mapping in both maps.
4. Alternative: Record the "last seen position" for each character. If lastSeenS[c1] != lastSeenT[c2], they aren't mapping consistently.

4. Example explanation

s = "egg", t = "add"

1. 'e' maps to 'a'. mapST={e:a}, mapTS={a:e}.
2. 'g' maps to 'd'. mapST={e:a, g:d}, mapTS={a:e, d:g}.
3. 'g' already mapped to 'd'. Matches t[2]. OK. Result: True. s = "foo", t = "bar"
4. 'f' -> 'b'.
5. 'o' -> 'a'.
6. 'o' already mapped to 'a', but t[2] is 'r'. Conflict! Result: False.

5. Common mistakes candidates make

• Single Map: Using only one map (s -> t), which fails when two different characters in s map to the same character in t (e.g., s="ab", t="aa").
• Ignoring Case: Not clarifying if the strings are case-sensitive.
• Complexity: Attempting a $O(N^2)$ solution by comparing all pairs of characters.

6. Interview preparation tip

Always remember that a one-to-one mapping requires bi-directionality. In any mapping problem, ask yourself: "Can two inputs map to the same output?" If the answer is no, you need to check both directions.