Isomorphic Strings

A substitution cipher replaces every letter with another letter, the same way every time. "paper" can become "title" under such a cipher: p becomes t, a becomes i, e becomes l, r becomes e. Two strings related like this are called isomorphic — they have the same pattern of repeats.

This problem looks like string manipulation, but it is really a test of whether you can keep a mapping consistent in both directions. It uses the index-map idea with a twist: the value stored is not a position but a decision you made earlier and must stick to.

The problem

You are given two strings, first and second. They are isomorphic if you can replace characters of first to get second, where every occurrence of a character is replaced by the same character, and no two different characters are replaced by the same character. A character may map to itself. Return whether they are isomorphic.

• "paper", "title" → True (p→t, a→i, e→l, r→e).
• "foo", "bar" → False. The first o would have to become a and the second o would have to become r.
• "badc", "baba" → False. b→b, then d→b as well: two characters of first would share one image.

Constraints: the strings have equal length up to 5 × 10⁴ and contain any printable ASCII characters.

Clarifying questions

• Are the lengths always equal? Assume yes, but return False if they are not — it costs one line.
• May a character map to itself? Yes. "ab" and "ab" are isomorphic.
• Is it case-sensitive? Yes; "A" and "a" are different characters.
• Two empty strings? Isomorphic — there is nothing to contradict.

Approach 1: compare every pair of positions

Two strings have the same shape exactly when, for every pair of positions i and j, "first repeats here" matches "second repeats here". So check all pairs.

1def is_isomorphic_brute(first: str, second: str) -> bool:2    """Every pair of positions must agree: equal in first iff equal in second."""3    if len(first) != len(second):4        return False5    n = len(first)6    for i in range(n):7        for j in range(i + 1, n):8            if (first[i] == first[j]) != (second[i] == second[j]):9                return False10    return True

Time: O(n²). Space: O(1).

This is a nice correct definition, and a good thing to say first because it states exactly what "same shape" means. At n = 5 × 10⁴ it is about 1.25 × 10⁹ pair checks, which is too slow.

The key insight

For position j, the brute force compares against every earlier position. But everything those comparisons tell you is already summed up in one fact: what did this character map to the last time I saw it? If first[j] appeared before and was mapped to some character, second[j] must be that same character. If it is new, it can map to anything — as long as nothing else has already claimed that target.

That "as long as nothing else has claimed it" is the part people miss. One map from first to second catches "foo"/"bar" (o cannot map to both a and r). It does not catch "badc"/"baba": b→b and d→b are two different keys, so a single forward map sees no conflict. A valid mapping must be one-to-one, so you also need the reverse map from second back to first.

A second view of the same idea: replace each character by the position where that character first appeared. "paper" becomes [0, 1, 0, 2, 3] and "title" becomes [0, 1, 0, 2, 3]. Two strings are isomorphic exactly when these patterns are equal. The pattern is one-to-one by construction, so it needs no reverse check.

Approach 2: two maps, one per direction

1def is_isomorphic(first: str, second: str) -> bool:2    """Two maps, one per direction, so the mapping is one-to-one."""3    if len(first) != len(second):4        return False5    forward: dict[str, str] = {}      # letter in first -> letter in second6    backward: dict[str, str] = {}     # letter in second -> letter in first7    for a, b in zip(first, second):8        if forward.get(a, b) != b or backward.get(b, a) != a:9            return False10        forward[a] = b11        backward[b] = a12    return True

The test forward.get(a, b) != b is compact, so read it slowly. If a has no mapping yet, get returns the default b, and the test passes. If a already maps to something, that something must be b. The backward test does the same from the other side.

Dry run on "badc" and "baba":

At position 2, the forward map alone is happy: d has never been seen. The backward map is what notices that b in second already belongs to b in first. On "paper"/"title" every row records or confirms (at position 2, p already maps to t and t already maps back to p), and the function returns True.

Time: O(n) — one pass, constant work per character. Space: O(k), where k is the number of distinct characters. With ASCII that is at most 128 per map, so O(1).

Notice what the maps replaced. The brute force asked, for each position, "which earlier positions hold the same character?" and compared all of them. The forward map stores the answer to every such question as it is decided, so each later position needs one lookup instead of a scan. That is the index-map idea again: the value stored is not a position but a promise made earlier, and each new character must keep it.

Approach 3: compare first-seen patterns

1def pattern_of(text: str) -> list[int]:2    """Replace each character by the order in which it first appeared."""3    first_seen: dict[str, int] = {}4    return [first_seen.setdefault(character, len(first_seen)) for character in text]567def is_isomorphic_by_pattern(first: str, second: str) -> bool:8    return len(first) == len(second) and pattern_of(first) == pattern_of(second)

setdefault returns the stored number if the character was seen before; otherwise it stores the next unused number and returns that. Numbering characters 0, 1, 2 in order of first appearance gives the same result as numbering by first position, and it is simpler to write.

Time: O(n). Space: O(n) for the two pattern lists. It uses more memory than Approach 2 and cannot stop early, but it has a real advantage: the pattern is a canonical key. Turn it into a tuple and you can group thousands of strings by shape with a grouping map, which two maps cannot do.

Edge cases

• Different lengths: "ab" and "a" return False at the length check.
• Empty strings: the loop never runs; True.
• Self-mapping: "egg" and "add": e→a, g→d, g→d again. True.
• The one-sided trap: "badc"/"baba" and its mirror "baba"/"badc". The mirror is caught by the forward map (b is mapped to b, then to d); the original needs the backward map. Test both directions.

Follow-ups

• Word Pattern: does "abba" match "dog cat cat dog"? The same two-map solution, with letters on one side and words on the other. First check that the number of words equals the number of letters.
• Group strings by shape: use tuple(pattern_of(s)) as the key of a grouping map. "paper", "title" and "xyxzw" land together.
• A fixed alphabet: replace the dicts with two arrays of size 128 (or 256), indexed by character code. Same logic, less overhead. It does not work for arbitrary Unicode — the dicts do.