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.

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

• Invariant: every mapped character pair must be consistent in both directions.
• The map counts/associations are updated consistently per element.
• Lookups use this exact state, so decisions are based on full prior data.
• Therefore the result is correct for the entire input.

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.

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.