Isomorphic Strings — Solution

Problem

Given two strings of equal length, determine whether the characters in one can be consistently remapped to reproduce the other. Each character in the first string must map to exactly one character in the second, and no two distinct characters in the first string may share the same target.

• Input: s = "paper", t = "title"
• Output: true
• Explanation: p→t, a→i, e→l, r→e — every character maps consistently through both strings with no collisions.

Counter-example: s = "ab", t = "aa" returns false because both 'a' and 'b' in s would need to map to 'a' in t, violating the one-to-one rule.

Intuition

The problem asks whether a bijection exists between the character sets of the two strings. A one-way mapping from s to t is not enough — without also tracking the reverse, two different characters in s could silently claim the same target in t. Maintaining two hash maps simultaneously catches conflicts in both directions in a single O(n) pass.

Solution — Bidirectional Hash Maps

Build two maps in lockstep: one from s→t and one from t→s. For each position, check both maps for conflicts before recording a new pair.

1. Initialize s_to_t and t_to_s as empty maps.
2. Walk through each character pair (char_s, char_t) together.
3. If char_s is already in s_to_t, verify it still maps to char_t; return false on mismatch.
4. If char_s is new, check whether char_t is already claimed by a different s-character in t_to_s; return false on conflict.
5. Record the new pair in both maps.
6. Return true after all pairs pass.

1def isIsomorphic(s: str, t: str) -> bool:
2    s_to_t = {}
3    t_to_s = {}
4    for char_s, char_t in zip(s, t):
5        if char_s in s_to_t:
6            if s_to_t[char_s] != char_t:
7                return False
8        else:
9            # char_t is already claimed by a different s-character
10            if char_t in t_to_s and t_to_s[char_t] != char_s:
11                return False
12            s_to_t[char_s] = char_t
13            t_to_s[char_t] = char_s
14    return True

Time: O(n) — one pass through both strings.
Space: O(1) — the maps hold at most one entry per distinct character; the alphabet is bounded so growth stops regardless of string length.

Complexity Summary

Common Mistakes

• Only mapping one direction — checking s→t alone lets s="ab", t="aa" return true incorrectly; 'a'→'a' and 'b'→'a' both succeed independently in a one-way map.
• Placing the reverse check outside the else branch — the t_to_s conflict check must only run when char_s is new. When s_to_t[char_s] already equals char_t, the reverse entry was set correctly the first time; checking it again in the outer scope adds no safety and can cause false failures.
• Using == on boxed Character objects in Java — comparing sToT.get(cs) == ct works only by coincidence for low-ASCII values due to Java's Character cache; the safe form compares against the primitive char variable directly (as the code above does), which forces auto-unboxing.
• Confusing isomorphic with anagram — anagrams require identical character frequencies ("ab" and "ba"); isomorphic strings require a consistent one-to-one mapping ("ab" and "cd"). The distinction changes which data structure is appropriate.
• Using an array indexed by character code instead of a hash map — an int[128] works for ASCII but its default value (0) collides with the sentinel you need for "unmapped", forcing an awkward -1 initialization or offset trick that obscures the intent.

Related Problems

• valid-anagram — same character-frequency hash map pattern, but checks equality of counts rather than a bijection
• find-all-anagrams-in-a-string — extends the character-map check across a sliding window over a larger string
• first-unique-character-in-a-string — builds a character frequency map in one pass, then scans for the first count-of-one entry
• two-sum — foundational hash map pattern: store seen values and query the map for a complement in a single pass
• word-ladder — character-level transformation tracking that similarly requires a visited-state map to avoid revisiting equivalent configurations