Isomorphic Strings - Solution & Explanation

Problem Overview: Given two strings s and t, determine whether they are isomorphic. Two strings are isomorphic if characters in s can be replaced to get t, with every character mapping to exactly one other character and preserving order.

The key constraint is one-to-one character mapping. A character from s cannot map to two different characters in t, and two different characters in s cannot map to the same character in t. Efficient solutions rely on tracking this mapping while scanning the strings once.

Approach 1: One-to-One Character Mapping (O(n) time, O(1) space)

Use two hash maps (or arrays for ASCII) to maintain a bidirectional mapping between characters in s and t. Iterate through both strings simultaneously. When you see characters s[i] and t[i], check whether an existing mapping conflicts with the current pair. If s[i] is already mapped to a different character, or t[i] is already mapped from another character, the strings are not isomorphic.

If no mapping exists yet, store the mapping in both directions. The scan finishes once every pair is validated. Each step performs constant-time hash lookups, giving O(n) time complexity and O(1) space (bounded by the character set). This approach relies heavily on hash table lookups and straightforward string traversal.

Approach 2: Unique Pattern Generation (O(n) time, O(n) space)

Another way to check isomorphism is to transform both strings into a canonical pattern representation. Iterate through each string and assign an incremental ID the first time you see a character. For example, the string paper becomes the pattern [0,1,0,3,4], and title produces the same sequence.

Build this pattern by maintaining a map from character to its first occurrence index or assigned ID. If both strings generate identical pattern arrays, they follow the same structural mapping and are therefore isomorphic. If the patterns differ at any position, the mapping rule is violated.

This technique still scans the string once, resulting in O(n) time complexity. Space usage becomes O(n) because you store the generated pattern sequence for comparison. The method is conceptually clean and useful when you want to reason about structural equivalence between strings.

Recommended for interviews: The One-to-One Character Mapping approach is what interviewers typically expect. It demonstrates understanding of bijective mappings and efficient use of hash tables with O(n) time. Pattern generation works well conceptually, but the bidirectional mapping solution is usually considered more direct and memory efficient.