AlgoMaster Logo

Isomorphic Strings

Frequency7 min readUpdated June 23, 2026

Understanding the Problem

At its core, this problem asks: can we create a one-to-one mapping (a bijection) between the characters of s and the characters of t?

The word "isomorphic" means "same structure." Two strings are isomorphic if they share the same character pattern. In "egg", the pattern is "ABB" (first character is unique, second and third are the same). In "add", the pattern is also "ABB". So they're isomorphic. But "foo" has pattern "ABB" while "bar" has pattern "ABC", so they're not.

The mapping must be bijective, meaning it must work in both directions. If 'a' maps to 'b', then no other character in s can map to 'b'. Consider s = "badc" and t = "baba": 'b' maps to 'b', 'a' maps to 'a', but then 'd' tries to map to 'b', which is already taken by 'b'. That is a conflict. A single forward map from s to t does not catch this, so the reverse mapping has to be enforced too.

Key Constraints:

  • 1 <= s.length <= 5 * 10^4 → With up to 50,000 characters, an O(n^2) approach would mean up to 2.5 * 10^9 operations, too slow for typical time limits. An O(n) solution is the target.
  • t.length == s.length → The strings are always the same length, so there is no length mismatch to handle.
  • s and t consist of any valid ASCII character → There are at most 256 distinct characters, so the map or array tracking characters is bounded by a constant regardless of input length.

Approach 1: Brute Force (Check Every Mapping)

Intuition

Isomorphism comes down to a consistency check: every occurrence of a character in s must map to the same character in t, and vice versa. The most direct way to enforce this without any extra data structure is to compare each position against every earlier position. For each pair (s[i], t[i]), scan all previous indices j. If s[i] equals s[j], then t[i] must equal t[j]. If t[i] equals t[j], then s[i] must equal s[j]. Either failure means the strings cannot be isomorphic.

Algorithm

  1. Iterate through each index i from 0 to n-1.
  2. For each index i, scan all previous indices j from 0 to i-1.
  3. If s[j] == s[i], check that t[j] == t[i]. If not, return false.
  4. If t[j] == t[i], check that s[j] == s[i]. If not, return false.
  5. If we finish all positions without a conflict, return true.

Example Walkthrough

1Initialize: check all (i, j) pairs for consistency. s = "foo", t = "bar"
0
f
1
o
2
o
1/6

Code

The repeated inner scan is the source of the O(n^2) cost. Each position re-derives a character's mapping from scratch instead of remembering it. Storing each mapping as it is discovered turns every lookup into O(1).

Approach 2: Two Hash Maps

Intuition

A hash map answers "what does this character map to?" in O(1), which removes the inner scan. One map alone is not enough, though.

Consider s = "badc" and t = "baba". Mapping only s to t gives b->b, a->a, d->b. Both 'b' and 'd' now map to 'b', which violates the one-to-one requirement, but a single forward map never sees the collision. Checking the reverse direction catches it.

The fix is two maps: one from s->t and one from t->s. At each position, both are checked. If s[i] already has a mapping that does not match t[i], that is a conflict. If t[i] already has a mapping that does not match s[i], that is also a conflict. When both checks pass, the position records the mapping and the scan continues.

Algorithm

  1. Create two hash maps: mapST (s character -> t character) and mapTS (t character -> s character).
  2. Iterate through each index i from 0 to n-1.
  3. Let charS = s[i] and charT = t[i].
  4. If charS is already in mapST and mapST[charS] != charT, return false.
  5. If charT is already in mapTS and mapTS[charT] != charS, return false.
  6. Otherwise, set mapST[charS] = charT and mapTS[charT] = charS.
  7. If we finish all positions without a conflict, return true.

Example Walkthrough

1Initialize: mapST = {}, mapTS = {}. s = "paper", t = "title"
0
p
1
a
2
p
3
e
4
r
1/7

Code

The two maps store explicit character-to-character pairs, but the only property that matters is whether matching positions in s and t share the same occurrence pattern. The next approach tracks that pattern directly by recording the last position each character appeared at, which avoids storing any mapping.

Approach 3: Last Seen Index

Intuition

Two strings are isomorphic if and only if, at every position, the two characters share the same occurrence history. The last position where s[i] appeared before must equal the last position where t[i] appeared before.

Take position 5 with s[5] = 'a'. If 'a' last appeared in s at position 2, then t[5] must also have last appeared at position 2 in t. If s[i] last appeared at index 2 while the matching character in t last appeared at index 3, the two characters have diverging histories and the strings cannot be isomorphic. New characters on both sides report the same "never seen before" marker, so they also match. This holds because consistent mappings force paired characters to repeat in lockstep, while a broken mapping shows up the first time one side repeats and the other does not.

The method needs no explicit character-to-character map, only two arrays holding the last seen index for each character.

Algorithm

  1. Create two arrays of size 256 (for ASCII), initialized to -1. Call them lastSeenS and lastSeenT.
  2. Iterate through each index i from 0 to n-1.
  3. If lastSeenS[s[i]] != lastSeenT[t[i]], the characters have different occurrence patterns, so return false.
  4. Update lastSeenS[s[i]] = i and lastSeenT[t[i]] = i.
  5. If we finish all positions without a conflict, return true.

Example Walkthrough

1Initialize: lastSeenS and lastSeenT all set to -1. s = "foo", t = "bar"
0
f
1
o
2
o
1/5

Code