Isomorphic Strings

Two strings s and t are isomorphic if the characters in s can be replaced to get t, with a one-to-one mapping (no two characters map to the same character).

Return true if s and t are isomorphic.

Why this is worth learning

A consistent forward mapping is not enough: two different source bytes must not collapse to one target byte. The reverse mapping enforces injectivity.

Before coding: one-minute experiment

Why is s="ab", t="aa" false even though a forward map can store a→a and b→a?

Function signature

func IsIsomorphic(s string, t string) bool

Inputs / outputs

• s, t: input strings of equal length.
• Return: true if isomorphic, else false.

Example

s = "egg", t = "add"
Output: true

s = "foo", t = "bar"
Output: false

Constraints

• 0 <= len(s) == len(t) <= 100_000
• Strings are ASCII.

Core idea (near-solution)

Track two mappings:

• s -> t
• t -> s

Invariant: every mapped character pair must be consistent in both directions.

Algorithm (step-by-step)

1. Initialize two maps (or fixed arrays) for forward and backward mapping.
2. For each position i:
   • If s[i] was mapped before, ensure it maps to t[i].
   • If t[i] was mapped before, ensure it maps to s[i].
   • Otherwise, create both mappings.
3. If all positions match, return true.

Correctness sketch

For every processed position, the forward and reverse maps agree with that byte pair. If neither byte has a mapping, adding both directions extends a one-to-one correspondence. If either direction already disagrees, no single bijection can explain both the earlier pair and this one. Otherwise the pair is consistent and leaves the invariant unchanged. At the end, the maps witness a replacement of every source byte producing the target, and the reverse map proves no two sources share a target. Conversely, any valid bijection would make every checked pair agree, so rejection cannot discard a valid isomorphism.

Trace (hand walkthrough)

Example input:
s = "egg", t = "add"
Output: true

s = "foo", t = "bar"
Output: false

Walk:
- "egg" vs "add": map e->a, g->d; all repeats consistent -> true
- "foo" vs "bar": map f->b, o->a, next o must map to a but sees r -> false

Pitfalls to avoid

• Only checking one direction (allows two letters to map to one).
• Forgetting to enforce equal length.

Debugging lens

Use repeated patterns such as egg/add and ab/aa. Sentinel -1 distinguishes an unmapped byte from byte value zero; a zero-filled table without a presence marker is unsafe.

Complexity

• Time: O(n)
• Extra space: O(1) for ASCII maps.

Implementation notes (Go)

• Use two maps to enforce a bijection (s->t and t->s).
• Update both maps at each position.

Reconstruction checkpoint

Why is s="ab", t="aa" false even though a forward map can store a→a and b→a?

Return to Hash Map · Module quiz