Isomorphic Strings
Verify a one-to-one character mapping between two strings, checking both directions
Problem Statement
Two strings s and t are isomorphic if the characters of s can be replaced to get t, where:
- Every occurrence of a character maps to the same character
- No two characters map to the same character
- A character may map to itself
Input: s = "egg", t = "add"
Output: true
Why: e → a, g → d
Input: s = "foo", t = "bar"
Output: false
Why: o would need to map to both 'a' and 'r'
Input: s = "badc", t = "baba"
Output: false
Why: d → b and b → b — two characters mapping to the same oneIntuition
The obvious half is easy: walk both strings together and record s[i] → t[i]. If a character is already mapped to something else, the strings are not isomorphic. That catches "foo" / "bar".
It does not catch "badc" / "baba".
Why one map is not enough
With only s → t, the string pair "badc" / "baba" builds {b: b, a: a, d: b, c: a} with no conflict — every character of s maps consistently.
But b and d both map to b, which rule 2 forbids. The mapping must be one-to-one (a bijection), not merely a function.
The key insight
Maintain two maps: s → t and t → s. Every position must be consistent with both.
The reverse map is what enforces "no two characters map to the same character" — it detects a t character that already has a different owner.
Real-world analogy
A substitution cipher. Each plaintext letter must always encrypt to the same ciphertext letter, and each ciphertext letter must decrypt back to exactly one plaintext letter. Without the second rule, decryption would be ambiguous.
Watch it run
Approach
At each position, check both
If forward already maps s[i] to something other than t[i] → false.
If backward already maps t[i] to something other than s[i] → false.
Solution
def is_isomorphic(s: str, t: str) -> bool:
"""True if s and t are related by a one-to-one character mapping."""
if len(s) != len(t):
return False
forward: dict[str, str] = {} # s char -> t char
backward: dict[str, str] = {} # t char -> s char
for a, b in zip(s, t):
if a in forward and forward[a] != b:
return False # a already maps somewhere else
if b in backward and backward[b] != a:
return False # b is already claimed by another character
forward[a] = b
backward[b] = a
return TrueA compact alternative using first-occurrence indices:
def is_isomorphic_index(s: str, t: str) -> bool:
# Two strings are isomorphic iff their patterns of first occurrences match.
return [s.index(c) for c in s] == [t.index(c) for c in t]Elegant, but str.index scans from the start each time, making it O(n²).
The single-map shortcut that actually works
Some solutions use one map plus a set of used target characters. That is equivalent — the set is a stripped-down reverse map that records only whether a target is taken, not by whom. Both enforce the bijection; two maps just make the symmetry explicit.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(k)
- Time — one pass with
O(1)map operations per character. - Space —
O(k)wherekis the alphabet size, bounded by the number of distinct characters. For ASCII that is at most 256, effectively constant.
Edge Cases
Related Problems
- Valid Anagram — matching multisets rather than structure
- Group Anagrams — canonical forms for string comparison
- Two Sum — hash maps recording relationships as you scan