Run it
The two-map version and the single-map version run side by side, on the input that separates them, plus the canonical-form alternative reaching the same verdicts.
Two maps, not one
O(n) time, O(k) space where k is the alphabet size.
Checking only forward accepts "badc" / "baba": b→b, a→a, d→b... which conflicts, so that particular pair is caught. But "ab" / "aa" is not — a→a and b→a are both consistent forwards, and they map two characters to one.
The second map is what enforces injectivity, and stating why it is needed — with a counterexample — is the substance of a good answer.
The pattern-normalisation alternative
An elegant one-liner: two strings are isomorphic exactly when their occurrence patterns match.
"egg" gives [0, 1, 1] and "add" gives [0, 1, 1] — equal, so isomorphic. "foo" gives [0, 1, 1] and "bar" gives [0, 1, 2] — different.
This automatically handles both directions, because the pattern is a canonical form. The catch is that x.index(ch) is O(n), making the whole thing O(nĀ²). Fixing it with a dictionary restores O(n):
Worth offering as the canonical-form view after the two-map version, because it is the same idea that solves the "group anagrams" family — normalise, then compare.
What isomorphic means here
There must be a one-to-one correspondence between the characters: replacing every character of the first string according to a fixed rule produces the second, and no two characters map to the same target. "Same shape, different letters".
A length check is a free first rejection, and the empty string is isomorphic to itself. The canonical-form view makes the whole thing one comparison: encode each string as the first-occurrence index of every character, so "paper" becomes [0, 1, 0, 2, 3] and "title" becomes [0, 1, 0, 2, 3] — identical, so isomorphic — while "foo" gives [0, 1, 1] and "bar" gives [0, 1, 2], which differ at the third position. Because the pattern is canonical it checks both directions at once, which is exactly what the two-map version needs a second map to do.
Why one map is not enough
Track only a → b and "badc" against "baba" passes: b→b, a→a, d→b, c→a — every forward rule is consistent, and two distinct characters have collapsed onto one target.
The reverse map catches it: b is already claimed by b, so d→b is rejected. Both directions are needed because a bijection is a constraint in both directions.
Normalise each string to the pattern of first appearances — "paper" and "title" both become [0,1,2,0,3] — and compare the patterns. One pass each, no paired bookkeeping, and it extends naturally to comparing many strings at once by using the pattern as a dictionary key.
That is the same "canonicalise, then compare" idea as grouping anagrams, which is worth pointing out.
Edge cases
| Case | Result |
|---|
| Different lengths | False — check first, it is O(1) |
| Both empty | True |
| Single characters | True, whatever they are |
| Same string | True — the identity mapping |
"aa" / "ab" | False — a cannot map to two characters |
"ab" / "aa" | False — needs the backward map |
| All distinct in both | True, if lengths match |
| Unicode | Works — dictionaries handle any hashable character |
The two "ab"/"aa" rows are the pair to test: one direction catches the first, and only the second map catches the second. Mentioning both demonstrates that the bijection requirement is understood rather than copied.
Word pattern. The same problem with words instead of characters: does "dog cat cat dog" match the pattern "abba"? Identical structure over s.split().
Group isomorphic strings. Use the normalised pattern as a dictionary key, exactly as sorted characters group anagrams. The canonical-form technique again.
Isomorphic graphs. Superficially related and vastly harder — graph isomorphism has no known polynomial algorithm. Worth knowing the distinction if it comes up, because the name invites confusion.
Find and replace with a consistent mapping. The practical version: applying a cipher or a tokenisation consistently.
| Problem | Canonical form |
|---|
| Isomorphic strings | First-occurrence index pattern |
| Anagrams | Sorted characters, or a count tuple |
| Rotations | Smallest rotation, or b in a + a |
| Case-insensitive equality | Casefolded string |
That table is the transferable lesson: when a problem asks whether two things are equivalent under some transformation, compute a canonical form and compare. It turns an equivalence test into a hash lookup, which is what makes grouping possible.
What it is testing
Do you require a bijection? The one-map solution is the trap, and the interviewer will have "ab" / "aa" ready.
Do you check lengths first? One line, O(1), and it avoids the whole loop.
Do you know it is order-sensitive? Isomorphism preserves position, unlike anagrams — conflating the two is a conceptual error.
Do you see the canonical-form view? Offering the pattern-normalisation solution shows you can reframe rather than only implement.
Is your index-based version O(n) or O(n²)? The elegant one-liner is quadratic, and noticing that is the difference between neat and correct.
Recap in one screen
- Isomorphic means a consistent one-to-one character mapping preserving order.
- Two dictionaries are required — forward and backward — or
"ab" / "aa" passes incorrectly. - O(n) time, O(k) space; check lengths first.
- Normalising each string to its first-occurrence index pattern gives a canonical form that handles both directions.
- Use
str.index inside a comprehension and the elegant version becomes O(n²); a dictionary restores O(n).