Isomorphic Strings

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)?