{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Isomorphic Strings – Solution & Complexity

Interview solutions
/
Isomorphic Strings

Solution Walkthrough

  1. Step 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. Step 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. Step 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. Step 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. Step 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. Step 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?