LeetCode 205 – Isomorphic Strings

Isomorphic Strings has a one-map solution that is wrong and a two-map solution that is right, and the gap between them is a single word in the problem statement. It is one of the cleanest examples on the list of an answer that passes every example you would think to try and fails on a three-character input.

The problem

Two strings are isomorphic if the characters of the first can be replaced to get the second, where the replacement is consistent and no two characters map to the same character. A character may map to itself.

"egg",   "add"    -> true    e→a, g→d
"foo",   "bar"    -> false   o would have to be both a and r
"paper", "title"  -> true    p→t, a→i, e→l, r→e
"badc",  "baba"   -> false   d→b and b→b: TWO characters mapping to b
"",      ""       -> true

"badc" / "baba" is the case that matters. Reading it left to right: b→b, a→a, d→b, c→a. Every character of the first string has a single consistent image — nothing contradicts. And it is still not isomorphic, because b and d both map to b.

The mapping must be a bijection

"No two characters may map to the same character" makes the mapping injective, and since it also has to cover the second string, it is a bijection between the characters used. A single map from s to t only enforces that each source character has one image — it says nothing about two sources sharing one.

forward map only:     s → t is a function          catches "foo"/"bar"
plus a reverse map:   t → s is also a function     catches "badc"/"baba"

So keep both, and check both on every character. The two together say exactly "this pairing is one-to-one in both directions", which is the definition.

Java

class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) return false;

        // Two maps, because the pairing must be one-to-one in BOTH directions.
        Map<Character, Character> forward = new HashMap<>();
        Map<Character, Character> backward = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            char a = s.charAt(i), b = t.charAt(i);

            Character mapped = forward.get(a);
            Character origin = backward.get(b);

            // Either both are unseen, or both already agree with this pairing.
            if (mapped == null && origin == null) {
                forward.put(a, b);
                backward.put(b, a);
            } else if (!Character.valueOf(b).equals(mapped)
                    || !Character.valueOf(a).equals(origin)) {
                return false;
            }
        }

        return true;
    }
}

The length check comes first. Without it, a shorter t throws on t.charAt(i) rather than returning false.

Character.valueOf(b).equals(mapped) rather than b == mapped. Comparing a char to a boxed Character with == unboxes and works — but comparing two boxed Character objects with == compares references, which is true only inside the cache range. Using equals throughout avoids having to reason about which case you are in.

Python

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        forward: dict[str, str] = {}
        backward: dict[str, str] = {}

        for a, b in zip(s, t):
            if a in forward and forward[a] != b:
                return False
            if b in backward and backward[b] != a:
                return False

            forward[a] = b
            backward[b] = a

        return True

Two independent guards read more clearly than one combined condition, and each maps directly to one direction of the bijection. Writing them separately is worth the extra line.

The first-occurrence trick

There is a neat one-liner that avoids maps entirely: two strings are isomorphic exactly when the positions of first occurrence agree at every index.

"paper"  first-occurrence indices:  0 1 0 3 1
"title"  first-occurrence indices:  0 1 0 3 1     equal -> isomorphic

"badc"   ->  0 1 2 3
"baba"   ->  0 1 0 1                              differ -> not isomorphic

In Python that is [s.index(c) for c in s] == [t.index(c) for c in t], which is elegant and O(n²) because index scans. It also captures the bijection correctly in both directions, which is the interesting part — the pattern of repetition is the isomorphism class.

Say it, note the quadratic, keep the two maps.

Complexity

Approach	Time	Space
Two maps	`O(n)`	`O(k)`, distinct characters
First-occurrence lists	`O(n²)`	`O(n)`

One pass, and the maps hold at most the alphabet — O(1) for ASCII. Two fixed int[128] arrays of last-seen indices are the constant-space version if the alphabet is bounded, and are what most published solutions use.

The pattern

Word Pattern (290) is this exact problem with words instead of characters — "abba" against "dog cat cat dog" — and the same two-map structure, including the same trap: a single map accepts "abba" / "dog dog dog dog".

The general recognition: whenever a problem says "consistent replacement" and adds "and no two map to the same", it is asking for a bijection, and a bijection needs two maps. The second clause is easy to skim past, and skimming past it is the whole trap.

What the interviewer is checking

That the mapping must be injective, not merely a function.
"badc" / "baba", or a case of your own that defeats one map.
The length check before indexing.
That a character mapping to itself is allowed.
Empty strings, and single characters.
Boxed-Character comparison in Java.
That you can connect it to Word Pattern.