Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Two strings are isomorphic if there is a consistent one-to-one (bijective) character mapping from s to t that preserves order. The canonical answer scans both strings together and enforces the mapping in BOTH directions: s→t must be consistent AND t→s must be consistent. One map is not enough — you need two maps (or a map plus a reverse-membership set). O(n) time, O(1) space (fixed alphabet).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognize that 'isomorphic' means a true bijection — not just that s maps to t, but that t maps back to s. The trap is settling for one hash map.
Where candidates slip
Using a single s→t map and forgetting the reverse, so `s = "badc", t = "baba"` wrongly returns true (both 'd' and 'c' would map to different chars, but two source chars are allowed to collide onto one target without the reverse check).
How to stand out
State up front 'isomorphic means bijection, so I need consistency in both directions', then mention the index-encoding trick (first-occurrence positions) as an alternative one-array solution.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewRead pair (s[i], t[i])s[i] already in mapST?YesNoExplore the full treeCollapse the tree
How to read it:The decision flow. The reverse check is the branch most candidates forget.
s = "egg", t = "add"How to read it:Forward map s→t shown filling; the reverse map mirrors it. Both stay consistent so we return true.
- Frame 1
i=0, e/aneither seen → map e→a (and a→e reverse)
e→ a - Frame 2
i=1, g/dneither seen → map g→d (and d→g reverse)
e→ ag→ d - Frame 3
i=2, g/dg seen → mapST[g]=d matches t[i]=d → OK
e→ ag→ dMatch found.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2 · Optimal
Two Hash Maps — Forward and Reverse (Optimal)
1Hint 1Explore hintHide hint
What does 'isomorphic' actually require? Not just that every s-char picks a t-char, but that no two s-chars pick the SAME t-char. That second condition is the one a single map can't express.
2Hint 2Explore hintHide hint
Keep two maps: mapST records what each s-char must become, mapTS records which s-char each t-char came from. Walk both strings in lockstep.
3Hint 3Explore hintHide hint
For each pair (a, b): if a is already mapped and disagrees with b, fail; if b is already claimed by some other source char, fail; otherwise record both directions.
A · Core idea
Walk s and t together, one index at a time. At position i we have a pair (a, b) = (s[i], t[i]) and we must enforce that the pairing is consistent with everything seen so far — in both directions.
Why two maps and not one. A single mapST answers the question "does `a` always become `b`?" That catches s = "foo", t = "bar" because the second o would have to become r while mapST[o] is already a. But it does not catch the reverse failure. Consider s = "badc", t = "baba". The forward map records b→b, a→a, then at the d/b pair it would happily add d→b — d has never been seen, so the forward check passes. The bug is that target b is now the image of two different source chars (b and d), which violates one-to-one. Only a reverse map mapTS, which already holds b→b, can reject d trying to claim b. This is the single most important insight in the problem: isomorphism is a bijection, and a bijection needs both halves verified.
Why we check before we write. At each step we first ask "is `a` already mapped, and if so does it still agree?" and "is `b` already claimed by a different source?" Only after both checks pass do we record mapST[a] = b and mapTS[b] = a. If we wrote first and checked later, the freshly written entry would always 'agree' with itself and the inconsistency would be masked — the same check-then-write discipline that the Two Sum hash map relies on.
Why O(1) space is the honest claim. The maps can never grow beyond the size of the alphabet. With ASCII that's at most 128 distinct keys in each map regardless of how long the strings are — a constant. So even though we allocate hash maps, the space is bounded by a constant, not by n. If an interviewer insists on calling it O(k) where k is the alphabet size, that's the same statement; the key point is it does not scale with input length.
Why lengths must match first. If s and t differ in length the strings cannot be isomorphic. In Java the loop bound makes this automatic only if you guard it; in Python zip truncates to the shorter string, so a length guard up front prevents "ab" and "a" from sneaking through.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
s = "badc", t = "baba"Hash-map state
i=0, f/b
fContinue scanning
f unseen → map f→b
falseC · Code with teaching comments
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The mental model is a phone book that must work both forward and backward: given a name you find exactly one number, and given a number you find exactly one name. A one-to-one mapping is precisely a pair of lookups that never contradict each other. Whenever a prompt says 'no two X map to the same Y', that phrase is your cue to add the reverse map.
ComplexityO(n) time, O(1) space — One pass over n characters, each doing O(1) average map operations → O(n) time. The maps hold at most one entry per distinct character of a bounded alphabet (≤ 128 ASCII) → O(1) space.
E · Edge cases and pitfalls7s = "a", t = "a" — Single pair a/a, neither map seen, record a→a, loop ends → true (char maps to itself).Explore edge casesHide edge cases
Edge cases handled
s = "a", t = "a"Single pair a/a, neither map seen, record a→a, loop ends → true (char maps to itself).s = "ab", t = "aa"a→a recorded; then b/a: a is already claimed in mapTS by source a → reverse conflict → false.s = "", t = ""Loop never runs → true (trivially isomorphic).
Pitfalls
- Using only a forward s→t map — passes badc/baba incorrectly.
- In Java, comparing Character objects with == can fail for values outside the cached range; use .equals or unbox to char as shown.
- Writing the mapping before checking — masks the conflict because the entry agrees with itself.
- Forgetting the length guard in Python — zip truncates and hides mismatched lengths.
Approach 2 of 2
Index Encoding — First-Occurrence Positions
1Hint 1Explore hintHide hint
Two strings are isomorphic exactly when the PATTERN of first-occurrence positions is identical. "egg" → [0,1,1] (e first at 0, g first at 1, repeats 1). "add" → [0,1,1]. Same pattern → isomorphic.
2Hint 2Explore hintHide hint
For each index i, compare the index of the most recent previous occurrence of s[i] with that of t[i]. If they ever differ, the strings aren't isomorphic.
3Hint 3Explore hintHide hint
Store last-seen index per character in two arrays/maps. Two chars that 'first appear' at the same relative moment must continue to align.
A · Core idea
This approach reframes isomorphism as a structural fingerprint. Instead of tracking which character maps to which, we track when each character last appeared. Two strings are isomorphic if and only if, at every index i, the last-seen position of s[i] equals the last-seen position of t[i].
Why this works. Encode each string as a sequence: at each position write down the index where the current character previously appeared (or a sentinel like 0 / "none" for a first appearance). For "egg" that sequence is [none, none, 1] — e is new, g is new, the second g last appeared at index 1. For "add" it is [none, none, 1] — identical. Two strings share the same fingerprint exactly when one can be relabeled into the other, because the fingerprint depends only on the repetition structure, not the actual letters. A bijection is precisely a relabeling that preserves repetition structure.
Why it needs no reverse map. The forward consistency and reverse consistency both fall out of comparing the same fingerprint for both strings simultaneously. If two source chars collided onto one target, their last-seen positions would diverge from the target's at the colliding index — the comparison catches it without an explicit second map. The two last-index tables are bookkeeping for a single comparison, not two independent mappings.
Why it's a nice thing to mention. It demonstrates you understand what isomorphism is at a structural level rather than mechanically applying two maps. In interviews, offering a second, conceptually different solution after the canonical one is a strong differentiator. The trade-off: it's slightly trickier to get the sentinel right (use 1-based indices or a clearly out-of-range marker so 'never seen' is distinguishable from 'seen at index 0').
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
s = "paper", t = "title"i=0, p/t
both never seen (0==0) → record lastS[p]=1, lastT[t]=1
alignedtrueC · Code with teaching comments
Reference implementation previewpublic boolean isIsomorphic(String s, String t) { if (s.length() != t.length()) return false; int[] lastS = new int[256]; int[] lastT = new int[256]; for (int i = 0; i < s.length(); i++) {Explore the full codeHide the full code
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Isomorphism is invariance of repetition structure under relabeling. Encoding each string by 'where did this char last appear' projects away the actual letters and keeps only that structure — so equality of encodings IS isomorphism. This 'normalize to a canonical form, then compare' trick generalizes far beyond strings.
ComplexityO(n) time, O(1) space — Single pass, O(1) array updates per char → O(n) time. Two fixed-size last-index tables of 256 entries → O(1) space.
E · Edge cases and pitfalls5s = "egg", t = "add" — Fingerprints [0,0,1] match → true.Explore edge casesHide edge cases
Edge cases handled
s = "egg", t = "add"Fingerprints [0,0,1] match → true.s = "badc", t = "baba"At i=2 lastS[d]=0 but lastT[b]=1 (b last seen at index 0) → 0 != 1 → false.
Pitfalls
- Using 0 as a real index AND as the 'unseen' sentinel — store i+1 to disambiguate.
- Sizing the array to 26 when the alphabet is full ASCII — use 128/256.
- Comparing actual indices instead of 'last seen' indices — you must compare repetition, not absolute position.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic boolean isIsomorphic(String s, String t) { if (s.length() != t.length()) return false; Map<Character, Character> mapST = new HashMap<>(); Map<Character, Character> mapTS = new HashMap<>(); for (int i = 0; i < s.length(); i++) {Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Only checking one direction
A single s→t map allows two distinct source chars to map to the same target. On s="badc", t="baba", d→b is added without complaint because d was never seen, even though b is already a target.
Explore the code comparisonHide the code comparison
Only checking one direction
A single s→t map allows two distinct source chars to map to the same target. On s="badc", t="baba", d→b is added without complaint because d was never seen, even though b is already a target.
Don't write this
Map<Character,Character> m = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char a = s.charAt(i), b = t.charAt(i);
if (m.containsKey(a) && m.get(a) != b) return false;
m.put(a, b);
}
return true;Write this instead
Map<Character,Character> mapST = new HashMap<>();
Map<Character,Character> mapTS = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char a = s.charAt(i), b = t.charAt(i);
if (mapST.containsKey(a) && mapST.get(a) != b) return false;
if (mapTS.containsKey(b) && mapTS.get(b) != a) return false;
mapST.put(a, b);
mapTS.put(b, a);
}
return true;2Comparing boxed Characters with ==
mapST.get(a) returns a Character object. Using != compares references, which only happens to work for cached values -128..127. For arbitrary chars it can give wrong answers. Unbox to char or use .equals.
Explore the code comparisonHide the code comparison
Comparing boxed Characters with ==
mapST.get(a) returns a Character object. Using != compares references, which only happens to work for cached values -128..127. For arbitrary chars it can give wrong answers. Unbox to char or use .equals.
Don't write this
Character mapped = mapST.get(a);
if (mapped != b) return false;Write this instead
if (mapST.get(a) != null && mapST.get(a).charValue() != b) return false;3Sentinel collision in index encoding
If you store the raw index i and use 0 to mean 'unseen', a character genuinely first seen at index 0 is indistinguishable from one never seen. Store i+1.
Explore the code comparisonHide the code comparison
Sentinel collision in index encoding
If you store the raw index i and use 0 to mean 'unseen', a character genuinely first seen at index 0 is indistinguishable from one never seen. Store i+1.
Don't write this
last_s[a] = i
if last_s.get(a, 0) != last_t.get(b, 0): ...Write this instead
last_s[a] = i + 1
if last_s.get(a, 0) != last_t.get(b, 0): ...Revise
Carry the pattern into the interview
Pattern to remember
Bijection check with two maps (forward + reverse)
Code pattern to memorize
for (a, b) in zip(s, t):
if a in mapST and mapST[a] != b: return False
if b in mapTS and mapTS[b] != a: return False
mapST[a] = b
mapTS[b] = a
return TrueRules to remember
- 1Check both directions. One map (s→t) lets
"badc" → "baba"pass incorrectly because two different source chars collide onto the same target. - 2Enforce consistency before overwriting: if
aalready maps to something other thanb, fail immediately. - 3Lengths must be equal first —
s.length() != t.length()is an instantfalse(zip silently truncates, so guard it explicitly in Python). - 4Mapping is positional: the i-th char of s must map to the i-th char of t, every time it appears.
- 5O(1) space is the honest claim — the alphabet is fixed (ASCII / Unicode-bounded), so the maps never exceed a constant.
Use this pattern when
- Asked whether one sequence can be relabeled into another, preserving order and repetition
- Structural / shape equality of two strings rather than literal equality
- Any 'consistent substitution cipher' style question
- You see repeated characters that must always translate the same way
Choose another pattern when
- Only one-directional mapping is required → a single map suffices (rare; re-read the prompt)
- Order does not matter, only multiset of chars → anagram / frequency count instead
- Mapping can be many-to-one → it is not isomorphism, drop the reverse check
- You need the actual mapping output, not a boolean → store and return the dict
Interview takeaway
Isomorphism = bijection = mapping consistent in both directions. The single most common bug is checking only s→t. Hold both maps and the problem collapses to a one-pass scan. The same two-map idea powers Word Pattern (LC 290) and any 'consistent relabeling' question.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternBijection via two hash maps. Recognise it whenever a prompt demands a consistent, one-to-one relabeling that preserves order — the giveaway phrase is 'no two characters may map to the same character'. The same forward+reverse discipline appears in Word Pattern and Find and Replace Pattern.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Word PatternSame bijection idea, but between pattern characters and whole words. Split on spaces, then two maps.
- Valid AnagramWhen order doesn't matter and only the multiset of chars counts — frequency map instead of bijection.
- Group AnagramsCanonical-form trick: normalize each string to a key, then group — like the index-encoding fingerprint here.
- Find and Replace PatternComing soonIsomorphism applied to a list of words against one pattern — reuse the two-map check per word.