Isomorphic Strings
WHAT IT SAYS
Two strings are isomorphic if the characters of one can be consistently replaced to produce the other, with no two characters mapping to the same character.
WHAT IT'S REALLY ASKING
"The letters themselves are irrelevant — what has to match is the SHAPE: where the repeats fall. And a relabeling that preserves repeats has to preserve them in both directions, because a relabeling is invertible. So the question is not 'does a mapping exist' but 'does it survive being read backwards'."
Try every possible relabeling
O(k! * n) time for an alphabet of size kEnumerate the bijections between the two alphabets, apply each to s, and check whether any of them produces t.
WHERE THE WORK IS WASTED — There is nothing to search. The very first occurrence of a character already forces where it must go: if s[0] is 'a' and t[0] is 'x', then a maps to x, full stop — no other bijection could possibly work. Every subsequent occurrence either confirms that or kills the whole attempt. So the candidate set has exactly one member, and you are enumerating k! of them to find it. Construct the mapping, do not search for it.
Isomorphic means the same shape — and shape is symmetric.
A relabeling is a bijection on characters. Bijections cannot merge things and cannot split things, so they cannot move a repeat. Concretely: if s[i] equals s[j], then after relabeling t[i] must equal t[j]. And because a bijection is invertible, the converse holds too — if t[i] equals t[j], then applying the inverse relabeling forces s[i] to equal s[j]. So the real condition is an 'if and only if', running in both directions: s[i] == s[j] IF AND ONLY IF t[i] == t[j], for every pair of positions. That is a statement purely about the pattern of repeats — the shape — and it is perfectly symmetric in s and t. It has to be, because 'isomorphic' is a symmetric relation. Now see the trap. A single forward map from s-characters to t-characters enforces only the first arrow: same character in s always becomes the same character in t. It says NOTHING about two different s-characters colliding onto the SAME t-character. Take s = 'badc' and t = 'baba': b to b, a to a, d to b, c to a. Every rule is consistent, the forward map never complains, and the strings are not isomorphic — because in t, position 0 and position 2 both hold 'b' while in s they hold different letters. The shape is broken and the forward map cannot see it. The second arrow is not defensive coding. It is half the definition, and the cheapest way to enforce it is to maintain the backward map and check it too.
Two maps, one pass
O(n) time, O(k) space for the two maps, with an early exit on the first contradictionWalk both strings together. At each position, if s[i] is already mapped, its image must equal t[i]; if t[i] already has a preimage, that preimage must equal s[i]. Any violation of either check fails immediately. Otherwise record both directions and continue.
Compare canonical shapes instead
O(n) time, O(k) space, always reads both strings in fullRewrite each string as its pattern of repeats — replace every character by how long ago you last saw it (or by the index of its first occurrence). 'paper' and 'title' both become 0,1,0,2,3. Two strings are isomorphic exactly when their patterns are identical, and this version is symmetric by construction, so the two-arrow trap cannot bite you.
Canonical Shape, Forced Mapping
YOU'LL SEE IT AGAIN WHEN
- The question is 'does a relabeling exist' rather than 'find the best one', and the first occurrence of each symbol already forces its image — so the candidate mapping is unique.
- The required relation is a bijection, not merely a function, which means a single map only checks half of it.
- You could replace each element with a structural fingerprint — position of last occurrence, sorted signature, degree sequence — and compare fingerprints instead of searching for the mapping.