Isomorphic Strings

Explanation & Solution

Description

Given two strings s and t, determine if they are isomorphic.

Two strings s and t are isomorphic if the characters in s can be replaced to get t, with a consistent one-to-one mapping. All occurrences of a character must be replaced with the same character while preserving the order. No two characters may map to the same character, but a character may map to itself.

Input: s = "egg", t = "add"

Output: true

Explanation: The mapping is: 'e' -> 'a', 'g' -> 'd'. Each character in s maps to exactly one character in t and vice versa.

Constraints

1 <= s.length <= 5 * 10⁴
t.length == s.length
s and t consist of any valid ASCII character

Approach

Hash Maps pattern

1. Handle Length Check

If s and t have different lengths, they cannot be isomorphic — return false

2. Create Two Hash Maps

mapST maps characters from s to t
mapTS maps characters from t to s
Two maps are needed to enforce the bijection (one-to-one and onto)

3. Iterate Through Both Strings

For each index i, take the character pair (s[i], t[i])

4. Check Existing Mappings

If s[i] is already mapped in mapST but to a different character than t[i], return false
If t[i] is already mapped in mapTS but to a different character than s[i], return false
These checks prevent both one-to-many and many-to-one mappings

5. Record the Mapping

Add s[i] -> t[i] to mapST
Add t[i] -> s[i] to mapTS

6. Return True

If the loop completes without conflicts, the strings are isomorphic

Key Insight

A single map is not enough. For example, with s = "badc" and t = "baba", a single map from s to t would not catch that both 'a' and 'c' map to 'a'. The reverse map catches this conflict.

Time

O(n)single pass through both strings

Space

O(1)the maps hold at most 256 ASCII characters, which is constant

Visualization

Input:

[e, g, g], t = add

—

No animation available

Left (L)Right (R)ConvergedDone

0 steps

Solution Code

Top K Frequent Elements

Word Pattern