Isomorphic Strings — The Two-Way HashMap Bijection FAANG Loves

Problem Statement#

Given two strings s and t, return true if they are isomorphic. Two strings are isomorphic if characters in s can be replaced to obtain t, with each character mapping to exactly one other character (and vice versa).

Constraints:

• 1 <= s.length <= 5 * 10^4
• t.length == s.length
• Strings consist of any valid ASCII characters.

Input:  s = "egg", t = "add"
Output: true

Input:  s = "foo", t = "bar"
Output: false

Why This Problem Matters#

LeetCode 205 Isomorphic Strings tests bijection thinking — the two-way map check that distinguishes a strong hashmap interview answer from a partial one. Google, Amazon, Microsoft, and Meta interviewers grade this as a "did the candidate remember the reverse mapping?" signal. Many candidates submit the forward map only and fail on cases like s = "ab", t = "aa".

The bijection pattern extends to Word Pattern (LC 290), encoding correctness in cipher problems, and graph isomorphism heuristics. In production, the same idea backs schema migration validators, secret rotation guards, and ID alias maps.

Hash table FAANG fluency means recognizing that "consistent mapping" requires injectivity in both directions, not just one.

The Core Insight#

A valid isomorphism requires two simultaneous invariants:

1. Forward map s_to_t[s[i]] is t[i] and never anything else.
2. Reverse map t_to_s[t[i]] is s[i] and never anything else.

Walk both strings in lockstep, updating both maps and checking for conflicts. The first conflict returns false.

A clever single-pass alternative encodes each string by first-seen index (paper -> 0,1,0,2,3) and compares the encodings, but the two-map version is the cleanest interview answer.

Visual Dry Run#

Input s = "paper", t = "title":

No conflict — return true.

Solution (Optimal)#

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        s_to_t: dict[str, str] = {}
        t_to_s: dict[str, str] = {}
        for cs, ct in zip(s, t):
            if s_to_t.get(cs, ct) != ct:
                return False
            if t_to_s.get(ct, cs) != cs:
                return False
            s_to_t[cs] = ct
            t_to_s[ct] = cs
        return True

var isIsomorphic = function(s, t) {
    const sToT = new Map();
    const tToS = new Map();
    for (let i = 0; i < s.length; i++) {
        const cs = s[i], ct = t[i];
        if (sToT.has(cs) && sToT.get(cs) !== ct) return false;
        if (tToS.has(ct) && tToS.get(ct) !== cs) return false;
        sToT.set(cs, ct);
        tToS.set(ct, cs);
    }
    return true;
};

Time: O(n) one pass with O(1) hash ops. Space: O(k) where k is the alphabet size, bounded by 256 for ASCII.

Common Mistakes#

• Using only a forward map. Misses cases where two source chars collide on the same target.
• Tracking targets with a Set instead of a reverse map. Detects collisions but cannot verify position-consistent mappings.
• Confusing isomorphic with anagram. Anagrams need character multiset equality; isomorphic needs a bijection.
• Forgetting the case where a character maps to itself, e.g., s = "aa", t = "aa".
• Mutating one map without the other; both must be updated together.

Interview Tips#

• State the bijection invariant explicitly before coding. Interviewers grade clarity.
• Use sentinel comparisons via dict.get(k, default) to avoid extra if branches.
• Mention the alternative canonical-encoding trick for senior rounds.
• Note that ASCII gives O(1) space (256-element arrays) versus O(k) for arbitrary alphabets.

Follow-up Questions#

• Generalize to Word Pattern (LC 290). (Hint: split pattern into words; same bijection logic.)
• How would you check graph isomorphism? (Hint: NP-hard in general; subtree hashing for trees.)
• Can you do it with a single map? (Hint: store encoded indexes for each character.)
• What if the alphabet is Unicode? (Hint: use HashMap; same algorithm.)
• How do you handle isomorphism over numeric arrays? (Hint: same bijection logic; keys are integers.)

Key Takeaways#

• LeetCode 205 Isomorphic Strings requires a two-way HashMap bijection check.
• A forward-only map fails on inputs like ab to aa where two source chars share a target.
• Maintain s_to_t and t_to_s together; conflict in either returns false.
• The pattern extends directly to Word Pattern (LC 290).
• Time is O(n); space is O(k) bounded by alphabet size.
• The canonical-encoding trick (first-seen index) gives an alternative single-pass solution.
• Bijection thinking shows up in cipher correctness, schema mapping, and graph isomorphism.