Isomorphic Strings and Word Pattern: The Two-Map Trick Interviewers Love
3 views
"Given two strings s and t, decide whether they are isomorphic." It sounds like a warm-up, and it often is the first question of a phone screen. Yet a surprising number of candidates fail it, not because the idea is hard, but because they only check one direction of the mapping. This note walks through the problem, its close cousin Word Pattern, and how to talk through both in a live interview.
What the question really asks
Two strings are isomorphic if you can replace every character in s with some character to get t, where the replacement is consistent and no two different characters map to the same target. "egg" and "add" are isomorphic (e->a, g->d). "foo" and "bar" are not, because o would need to map to both a and r. "badc" and "baba" are the classic trap: b->b, a->a, d->b, c->a. Every forward mapping is consistent, but two different source letters (b and d) both map to b. That is why a single dictionary is not enough.
The two-map solution
Walk through both strings at the same time. Keep one map from s to t and another from t to s. For each index i:
1. If s[i] is already mapped and the mapping is not t[i], return false.
2. If t[i] is already mapped back and the reverse mapping is not s[i], return false.
3. Otherwise record both mappings.
If you reach the end, return true. Time is O(n), and space is O(k), where k is the alphabet size, which is effectively constant for ASCII.
A tidy alternative is to compare "first-seen index" signatures: transform each string into a list where every character is replaced by the index of its first occurrence. "egg" becomes [0,1,1], "add" becomes [0,1,1], and equal signatures mean isomorphic. Mentioning both approaches shows range without wasting time.
Word Pattern: same idea, different tokens
Word Pattern asks whether a pattern like "abba" matches a sentence like "dog cat cat dog". Split the sentence into words, check that the number of words equals the pattern length (a frequent missed edge case), then apply the same two-map bijection check with characters on one side and words on the other.
How to present it under pressure
- Start with a failing example such as "badc"/"baba" before coding. It proves you understand why one map fails.
- Say the invariant out loud: "the mapping must be one-to-one in both directions."
- Name the edge cases: different lengths, empty strings, and Unicode if the interviewer cares.
- After coding, dry-run one true and one false example rather than declaring victory.
Follow-ups you might get
Interviewers sometimes ask you to group a list of words by pattern (use the signature as a hash key) or to handle a stream where characters arrive one at a time (keep the maps and answer incrementally). Both reuse the same core idea, which is the point: they want to see you recognise the bijection.
If you freeze on easy questions like this during a live round, practice helps, and so can a little support in the moment. Linkjob AI (https://linkjob.ai) gives real-time help during live job interviews and technical interviews, prompting you with structure and edge cases while you stay in control of the explanation.