vizlearn

Isomorphic strings

Interview QuestionsBy Updated

Walk both strings together, maintaining two maps: a → b and b → a. Every pair must agree with both. One map alone allows two characters to collapse onto one, so it wrongly accepts "badc" and "baba" — which is exactly the case interviewers test.

Overview

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.

StringsCoding problemMedium

Step through it

What to watch

  • Each step checks the pair against both maps.
  • A character already mapped elsewhere fails immediately.
  • The two maps at the end are inverses of each other.

Say this out loud

"Two dictionaries, one each way, because the mapping has to be a bijection. With only the forward map you'd accept two letters mapping onto the same one."

Isomorphic strings

Do two strings have the same character pattern? 'egg' and 'add' do; 'foo' and 'bar' do not.

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.

The canonical-form alternative

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.

Run it in Python

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.

isomorphic.pyPython 3
Output
How the code works
  1. forward.setdefault(x, y) != yInsert on first sight, compare on every later sight, in one expression. If x already maps somewhere else, this is the check that catches it.
  2. backward.setdefault(y, x) != xThe direction people omit. Without it two distinct characters can map onto the same target, and "badc"/"baba" passes.
  3. zip(a, b)Walks both together and stops at the shorter, which is why the length check has to come first — otherwise "ab" and "a" would compare equal on their overlap.
  4. seen.setdefault(ch, len(seen))The canonical form: each new character gets the next number, so the tuple describes the shape rather than the letters. Same idea as the anagram key.
Change one thing
  • Add ("abcd", "aabb"). Two characters collapsing onto one is exactly what the reverse map exists to reject.
  • Use the pattern as a dictionary key to group many strings by shape in one pass — the same move as grouping anagrams.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 3
Answer without scrolling back up.
  1. Why are two maps needed rather than one?
  2. The canonical-form approach compares:
  3. Why must the length check come before zip?





 Cheat sheet
Isomorphic strings
Walk both strings together, maintaining two maps: a → b and b → a. Every pair must agree with both. One map alone allows two characters to collapse onto one, so it wrongly accepts "badc" and "baba" — which is exactly the case interviewers test.
INTERVIEW · vizlearn.in/interview/isomorphic-strings.html
More in Interview
InterviewWhat is a Python list underneath?InterviewWhy does [[0]*3]*3 break?InterviewWhy is `in` slow on a list but fast on a set?InterviewTwo Sum
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact