A schema mapper treated two codes as the same shape if each letter in s had a partner in t. The first version stored only s → t. "egg" lined up with "add". "ab" lined up with "aa" too — until someone noticed a on the t side now had two partners.

Isomorphic Strings asks whether there is a bijection from characters in s onto characters in t. A hash table already gives you a partner lookup. One map uses that and still misses the reverse collision. Two maps — or two last-seen indexes — refuse it.

This is an interview writeup, not a hashing lecture. The hash-table post owns buckets and collisions. Here we only care about recording both directions so "ab" / "aa" is a false, not a silent overwrite.

The problem

Given two strings s and t of the same length, return true if they are isomorphic: you can replace characters in s to get t. The replacement is one-to-one. The same letter in s always becomes the same letter in t, and no two letters in s become the same letter in t.

s = "egg",   t = "add"    →  true
s = "foo",   t = "bar"    →  false
s = "paper", t = "title"  →  true
s = "badc",  t = "baba"   →  false   d and b collide the other way
s = "ab",    t = "aa"     →  false   two letters in s, one in t

Note: A single s → t map accepts "ab" / "aa": a → a, then b → a. The forward direction never complains. The inverse does: t’s a cannot partner both a and b.

Nested uniqueness is the honest brute force

For each index i, scan every earlier j. If s[i] == s[j] but t[i] != t[j], the forward map broke. If s[i] != s[j] but t[i] == t[j], two letters collapsed onto one. Correct. Quadratic.

boolean isIsomorphicNested(String s, String t) {
    int n = s.length();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if ((s.charAt(i) == s.charAt(j)) != (t.charAt(i) == t.charAt(j))) {
                return false;
            }
        }
    }
    return true;
}

At n = 20 this is a rounding error. At n in the hundreds of thousands you paid nested scans for a question two maps answer in one pass: does this letter already have a different partner — either way?

Two maps: partner both ways

If the lengths differ, return false. Otherwise two HashMaps: sToT and tToS.

  • Let a = s.charAt(i), b = t.charAt(i).
  • If a already maps and the partner is not b, false.
  • If b already maps and the partner is not a, false.
  • Record both and continue.

You never restart a nested scan. You never trust one direction.

s = "egg"   t = "add"

i=0  e→a, a→e
i=1  g→d, d→g
i=2  g already → d, t[2]=d  match
true
s = "badc"   t = "baba"

i=0  b→b, b→b
i=1  a→a, a→a
i=2  d wants → b, but t's b already maps to s's b, not d
false

The Java is that walk:

boolean isIsomorphic(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    Map<Character, Character> sToT = new HashMap<>();
    Map<Character, Character> tToS = new HashMap<>();
    for (int i = 0; i < s.length(); i++) {
        char a = s.charAt(i);
        char b = t.charAt(i);
        Character mapped = sToT.get(a);
        if (mapped != null && mapped != b) {
            return false;
        }
        Character inverse = tToS.get(b);
        if (inverse != null && inverse != a) {
            return false;
        }
        sToT.put(a, b);
        tToS.put(b, a);
    }
    return true;
}

Time is expected O(n) — one pass, a constant number of lookups and puts per index. Space is O(k) for the distinct characters, which is O(1) on a bounded alphabet. Worst-case hash degeneration is the hash-table post; do not re-lecture it at the board unless they ask.

Two last-seen-index arrays are the same bijection without HashMap objects: if s[i] and t[i] last appeared at different positions, the pairing already diverged. Store i + 1 so 0 still means unseen.

Note: One forward map is not a bijection. A map plus a set of used t letters is also correct if you reject a new s letter whose t partner is already claimed. Interviewers still want you to name the reverse collision out loud.

What interviewers usually poke next

  • Last-seen indexes. Two int[256], same loop, no HashMap. ASCII only; Unicode makes the 256-slot array a lie and the maps still work.
  • Word Pattern. Same bijection, tokens instead of characters. The trap is still one map.
  • Two empty strings. Length 0 equals 0, both maps stay empty, return true. Do not invent a special case unless they ask.
  • Same string. The identity mapping is legal. "foo" / "foo" is true; "foo" / "bar" is still false because o cannot partner both a and r.

You are done with this problem when you can say, out loud, why a nested uniqueness check is correct, why one HashMap accepts "ab" / "aa", and why the second map (or the second last-seen array) is the bijection, not decoration.