Isomorphic Strings
Isomorphic Strings: decide whether the characters of one string can be replaced consistently to produce another, preserving order.
- 1 <= s.length <= 5 * 10⁴
- t.length == s.length
- s and t consist of any valid ascii character.
Intuition
For isomorphic strings you will map s -> t and stop there, because that is what 'replace the characters' sounds like. It is half a check. Feed it s = 'badc', t = 'baba': b→b, a→a, then d→b and c→a are both brand new keys on the left, so a single forward map accepts them happily — even though b and d have now collapsed onto the same target letter, and so have a and c. Isomorphism is a BIJECTION, not just a function: distinct source characters must land on distinct targets, or the mapping cannot be undone. So carry the reverse map too, and at each index reject if fwd[s[i]] disagrees with t[i] OR rev[t[i]] disagrees with s[i]. Equivalently, keep one map plus a set of already-claimed targets. The invariant is that after every index the two maps are exact inverses of each other, which is precisely the property a one-to-one renaming has to satisfy.
A valid mapping must be a bijection, so two dictionaries are needed — one each way. A single map allows two different characters to collapse onto the same target, which the problem forbids. Any "one-to-one correspondence" question needs both directions checked.
Approach
Before reading on: price up what the direct approach costs here, then ask what you are recomputing on every character that could be carried instead. Aim for O(n) time and O(1) space.
Reject on length first
If the strings differ in length, no character-by-character correspondence exists at all, so return False before allocating anything. This also lets the main loop index both strings with a single counter without any bounds worry.
Maintain both directions
Keep fwd from characters of s to characters of t, and rev the other way. Walking the strings together, if s[i] is already in fwd its recorded image must equal t[i], and if t[i] is already in rev its recorded preimage must equal s[i]. The second condition is the one that catches the 'badc' / 'baba' collision, and it is why one map is not enough. When neither key exists, bind both at once so they stay inverses.
Fail fast, otherwise accept
Any single violated index is a complete disproof, so return False immediately rather than finishing the scan. If the loop completes, every character has a consistent partner in both directions and the strings are isomorphic. One pass over the input with maps bounded by the alphabet size gives O(n) time and O(1) space for a fixed alphabet.
Solution & live demo
Common pitfalls
Using only a forward map
if a in fwd and fwd[a] != b: return False fwd[a] = b
if b in rev and rev[b] != a: return False rev[b] = a
On "ab" and "aa" the forward map accepts a→a and b→a, but two characters mapping to one isn't isomorphic. The reverse map is what catches the collision.
Skipping the length check
for a, b in zip(s, t):
if len(s) != len(t):
return Falsezip silently stops at the shorter string, so "ab" and "abc" compare only the first two characters and report true. The lengths must match for a character-wise bijection to exist.
Comparing character index patterns with a subtle flaw
return [s.index(c) for c in s] == [t.index(c) for c in t]
fwd, rev = {}, {}The pattern comparison is actually correct, but str.index scans from the start each time, making it O(n²) — it times out on long inputs. Two dictionaries do the same job in one linear pass.
Edge cases
Return False up front; no mapping can exist between sequences of different sizes.
Fine. Identity is a perfectly valid bijection; nothing requires the mapped letters to differ.
The reverse map already holds that target under a different key, so the check fires and returns False — this is exactly the case a forward-only solution misses.
Lengths match, the loop body never runs, and True is returned; the empty mapping is trivially bijective.