{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsChat
New
Blog
Ctrl + K

Isomorphic Strings – Solution & Complexity

Interview solutions
/
Isomorphic Strings

Solution Walkthrough

1. Define isomorphism precisely

  • Each character of s must always translate to the same character of t.
  • The translation must be reversible: no two s characters share a t target.
  • That is a bijection between the characters that appear.

2. Track a single mapping (why it fails)

  • A common first attempt maps only s -> t.
  • That misses collisions like "ab" -> "aa", where two s characters map to the same t character.
  • We therefore need to guard both directions.

3. Maintain forward and backward maps

  • Walk both strings in lockstep.
  • For each pair (a, b), verify any existing a -> b and b -> a mappings still agree.
  • If a conflict appears, the strings are not isomorphic.

4. Two-map solution

  • forward maps characters of s to t; backward maps t back to s.
  • Reject as soon as either map disagrees with the current pair.
def is_isomorphic(s, t):
    if len(s) != len(t):
        return False
    forward, backward = {}, {}
    for a, b in zip(s, t):
        if a in forward and forward[a] != b:
            return False
        if b in backward and backward[b] != a:
            return False
        forward[a] = b
        backward[b] = a
    return True

5. Dry run

Trace s = "paper", t = "title".

iabforwardbackwardok?
0ptp->tt->pyes
1aia->ii->ayes
2ptconsistentconsistentyes
3ele->ll->eyes
4rer->ee->ryes

No conflict, so the answer is true.

6. Final solution and complexity

Two hashmaps enforce a bijection in O(n) time and O(1) extra space for a bounded alphabet.

def is_isomorphic(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    forward, backward = {}, {}
    for a, b in zip(s, t):
        if a in forward and forward[a] != b:
            return False
        if b in backward and backward[b] != a:
            return False
        forward[a] = b
        backward[b] = a
    return True

FAQ

See also

Practice Isomorphic Strings online (run code in the browser)Find All Anagrams in a String solution (medium)First Unique Character in a String solution (easy)Group Anagrams solution (medium)Longest Substring Without Repeating Characters solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?