Isomorphic Strings

Problem

Two strings s and t of equal length are isomorphic if there is a one-to-one substitution of characters that turns s into t: every occurrence of a character in s must map to the same character in t, and no two different characters of s may map to the same character of t. A character may map to itself.

Given s and t, return True if they are isomorphic and False otherwise.

Examples

• s = "egg", t = "add" → True — map e → a, g → d; the mapping is consistent and injective.
• s = "foo", t = "bar" → False — o would have to map to both a and r.
• s = "badc", t = "baba" → False — b → b and d → b would send two different characters to b, which the one-to-one rule forbids.

Constraints

• 1 <= len(s) <= 5 * 10^4
• t has the same length as s
• The strings may contain any valid ASCII characters.

Length 5 * 10^4 makes comparing all pairs of positions (O(n^2)) too slow; a single hashed pass is expected.

Think about it first

TL;DR

Two hash maps (one per direction) in a single pass — O(n) time, O(k) space for the alphabet.

Approach 1 — Brute force (pairwise consistency)

Isomorphism is equivalent to: for every pair of positions i, j, the characters of s match at those positions exactly when the characters of t do. Check all pairs.

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        n = len(s)
        for i in range(n):
            for j in range(i + 1, n):
                if (s[i] == s[j]) != (t[i] == t[j]):
                    return False
        return True

Complexity: O(n^2) time, O(1) space. At n = 5 * 10^4 that is ~1.25 * 10^9 comparisons — the constraints kill it outright.

Approach 2 — Two hash maps

The insight: the substitution can be built greedily in one pass, because the first time a character appears it must commit to its mapping forever. Two failure modes exist and each needs its own map: an s-character re-mapping to a new target (checked via s → t), and two s-characters colliding on one target (checked via t → s — this is what makes the mapping injective).

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

Walkthrough on s = "badc", t = "baba":

And on s = "egg", t = "add": e→a and g→d are recorded at their first occurrences; the second g/d pair agrees with both maps → True.

Complexity: O(n) time, O(k) space where k is the number of distinct characters (bounded by the alphabet, so effectively O(1)).

Approach 3 — First-occurrence signatures (zip-and-count)

The insight: s and t are isomorphic exactly when the pairing zip(s, t) never puts one character in two different pairs — i.e. the number of distinct pairs equals the number of distinct characters on each side. Three set sizes settle it.

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        return len(set(zip(s, t))) == len(set(s)) == len(set(t))

Walkthrough on s = "foo", t = "bar":

• set(zip(s, t)) = {('f','b'), ('o','a'), ('o','r')} → size 3 (the character o shows up in two different pairs, inflating the pair count).
• set(s) = {'f','o'} → size 2; set(t) = {'b','a','r'} → size 3.
• 3 == 2 is false → False. For "egg"/"add" the sizes are 2, 2, 2 → True.

Complexity: O(n) time, O(n) space in the worst case for the pair set. Same asymptotics as Approach 2 — terser, though it always scans everything and can’t fail fast mid-string.

Common pitfalls

• Checking only one direction: a single s → t map accepts s = "badc", t = "baba" even though two sources collide on b — the injectivity check (t → s, or the set(t) size) is mandatory.
• The tempting-but-wrong shortcut set(s) vs set(t) sizes alone: "ab" and "aa" have sizes 2 and 1 and fail correctly, but "ab" vs "ca" has sizes 2 and 2 while being isomorphic — equal alphabet sizes are necessary, not sufficient; you must also count the distinct pairs.
• Overwriting a map entry without checking it first — the first binding of a character is a permanent commitment; later occurrences may only confirm it.
• Assuming lowercase letters: the problem allows any ASCII characters, so fixed 26-slot arrays need to be sized to the full character range (hash maps sidestep this).

Pattern takeaway

“Consistent relabeling” problems reduce to building a bijection incrementally with a pair of hash maps — one per direction — where each element’s first appearance fixes its image and every later appearance is verified against it. Whenever a constraint is symmetric (“no two X share a Y” and “no two Y share an X”), expect to maintain both directions explicitly; checking one and hoping is the classic bug. The same double-map skeleton solves Word Pattern and friends.