Isomorphic Strings

Two strings are isomorphic if you can replace the characters of one to get the other — consistently, and with no two characters mapping to the same one.

isIsomorphic("egg", "add")     // true   e→a, g→d
isIsomorphic("foo", "bar")     // false  o→a and o→r
isIsomorphic("badc", "baba")   // false  d→b, but b→b already

One map is not enough

The obvious approach records s[i] → t[i] and checks it never changes. That catches "foo"/"bar", and it misses the third case above.

With one map, d → b looks fine — d has not been seen. But b is already spoken for, and two characters mapping onto the same one is not a substitution, it is a collapse.

Two maps, one pass

func isIsomorphic(s string, t string) bool {
    sRunes, tRunes := []rune(s), []rune(t)
    if len(sRunes) != len(tRunes) {
        return false
    }

    sToT := make(map[rune]rune)
    tToS := make(map[rune]rune)

    for i, sr := range sRunes {
        tr := tRunes[i]

        if mapped, ok := sToT[sr]; ok && mapped != tr {
            return false
        }
        if mapped, ok := tToS[tr]; ok && mapped != sr {
            return false
        }

        sToT[sr] = tr
        tToS[tr] = sr
    }

    return true
}

$O(n)$ time, $O(k)$ space in the alphabet size. Note len(sRunes), not len(s) — the guard bounds the slice it protects, which is the fix is subsequence needed.

The version to avoid, and why

A single map plus a scan for already-used values is also correct:

if _, ok := seen[r]; !ok {
    // Check whether target is already mapped
    for _, value := range seen {
        if value == target {
            return false
        }
    }
    seen[r] = target
}

It turns an $O(n)$ algorithm into $O(n \cdot k)$ — the inner scan runs on every new character, and with a large alphabet that is the dominant cost. The second map replaces that scan with a lookup, which is the same trade contains duplicate makes against a nested loop.

The trick worth stealing

Both strings can be reduced to a canonical form independently:

// Replace each character with the index of its first appearance.
func pattern(s string) []int {
    first := make(map[rune]int)
    out := make([]int, 0, len(s))
    for _, r := range s {
        if _, ok := first[r]; !ok {
            first[r] = len(first)
        }
        out = append(out, first[r])
    }
    return out
}

"egg" and "add" both become [0 1 1]; "foo" is [0 1 1] and "bar" is [0 1 2]. Two strings are isomorphic exactly when their patterns match.

This is canonicalisation again, and it has a property the pairwise check does not: the pattern is computed from one string alone, so you can group many strings by isomorphism in one pass instead of comparing them in pairs.