Isomorphic Strings

Next Permutation

Subarray Sum Equals K

Determine whether two strings share a consistent one-to-one character mapping in both directions.

Two strings `s` and `t` are isomorphic if the characters of `s` can be replaced to get `t` while preserving order.

Every occurrence of a character must map to the same character, and no two characters may map to the same character. A character may map to itself.

**Input / output**
- Input: `s: string`, `t: string`
- Output: `boolean`

**Examples**
1. `s = "egg"`, `t = "add"` returns `true` (`e->a`, `g->d`).
2. `s = "foo"`, `t = "bar"` returns `false` (`o` would map to both `a` and `r`).
3. `s = "paper"`, `t = "title"` returns `true`.

**Constraints**
- `0 <= s.length == t.length <= 50000`
- `s` and `t` consist of any Unicode characters (ASCII in the tests).

**Edge cases**
- Two empty strings are isomorphic.
- Mapping must be one-to-one in both directions, so `"badc"` and `"baba"` are not isomorphic.

**Target complexity**
- Aim for `O(n)` time and `O(1)` extra space (bounded alphabet).

**Hints**
1. Walk both strings together and remember the pairing seen for each character.
2. You need two maps: one from `s` to `t` and one from `t` to `s`.

**Follow-up**
How does this differ from checking whether the two strings follow the same repetition pattern (word pattern)?

- Each character of `s` must always translate to the same character of `t`.
- The translation must be reversible: no two `s` characters share a `t` target.
- That is a bijection between the characters that appear.

Define isomorphism precisely

- A common first attempt maps only `s -> t`.
- That misses collisions like `"ab" -> "aa"`, where two `s` characters map to the same `t` character.
- We therefore need to guard both directions.

Track a single mapping (why it fails)

- Walk both strings in lockstep.
- For each pair `(a, b)`, verify any existing `a -> b` and `b -> a` mappings still agree.
- If a conflict appears, the strings are not isomorphic.

Maintain forward and backward maps

- `forward` maps characters of `s` to `t`; `backward` maps `t` back to `s`.
- Reject as soon as either map disagrees with the current pair.

Two-map solution

Trace `s = "paper"`, `t = "title"`.

| i | a | b | forward | backward | ok? |
|---:|---|---|---|---|---|
| 0 | p | t | `p->t` | `t->p` | yes |
| 1 | a | i | `a->i` | `i->a` | yes |
| 2 | p | t | consistent | consistent | yes |
| 3 | e | l | `e->l` | `l->e` | yes |
| 4 | r | e | `r->e` | `e->r` | yes |

No conflict, so the answer is `true`.

Dry run

Two hashmaps enforce a bijection in `O(n)` time and `O(1)` extra space for a bounded alphabet.