Isomorphic Strings - Video Solutions

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 while preserving order. Each character must map to exactly one character, and no two characters can map to the same target character.

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

This approach enforces a strict one-to-one mapping between characters in the two strings using hash tables. Iterate through both strings simultaneously and maintain a mapping from s[i] to t[i]. If the character in s was seen before, verify that it maps to the same character in t. To prevent two characters mapping to the same target, maintain a second set or reverse map to track already-mapped characters.

The key insight is that isomorphic strings behave like a bijection: every source character must consistently map to one target character. Hash lookups make each validation constant time, so the entire scan runs in O(n). Space complexity is O(k), where k is the number of unique characters (bounded by the character set). This method relies heavily on a Hash Table for constant-time mapping and works well for general String problems involving character relationships.

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

Instead of directly mapping characters, convert each string into a structural pattern that represents how characters appear. Traverse the string and assign each new character an increasing index based on its first occurrence. For example, the string egg becomes the pattern [0,1,1], and add produces the same pattern.

Generate this pattern for both strings and compare the resulting sequences. If the patterns match, the strings are isomorphic. This works because the pattern encodes the structure of character repetition and ordering. Pattern generation uses a hash map to track first occurrences and builds an array of indices, giving O(n) time and O(n) space.

This method is conceptually clean and helpful when reasoning about structural equivalence between strings. It also generalizes well to problems where you compare patterns rather than raw characters.

Recommended for interviews: The one-to-one character mapping approach is what interviewers typically expect. It directly models the bijection requirement and demonstrates comfort with hash table lookups and constraint validation during iteration. Mentioning the pattern-generation method shows deeper understanding, but the mapping solution is simpler, uses less memory, and is the most common production implementation.