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.

def isIsomorphic(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, which exceeds the constraints.

Approach 2 — Two hash maps

Build the substitution greedily in one pass. The first time a character appears, its mapping is fixed; every later occurrence must match it. Two failure modes exist, each needing its own map: an s-character remapping to a new target (checked via s → t), and two s-characters colliding on one target (checked via t → s, which enforces injectivity).

def isIsomorphic(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)

s and t are isomorphic exactly when 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.

def isIsomorphic(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, but terser; it always scans the full input and cannot 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”), maintain both directions explicitly; checking only one is the classic bug. The same double-map structure solves Word Pattern.