Log inSign up
easyleetcodeNot Started

Isomorphic Strings

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

Problem Statement

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.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

Example 1 · Example:

Input: s = "egg", t = "add"
Output: true
Explanation: e -> a, g -> d. Valid bijection.

Example 2 · Example:

Input: s = "foo", t = "bar"
Output: false
Explanation: o maps to both a and r, which is invalid.

Example 3 · Example:

Input: s = "paper", t = "title"
Output: true
Explanation: p -> t, a -> i, e -> l, r -> e. Valid bijection.

Example 4 · Example:

Input: s = "badc", t = "baba"
Output: false
Explanation: b -> b, a -> a, d -> b (collision with b), invalid.

Constraints:

  • 1 <= s.length <= 5 * 104
  • t.length == s.length
  • s and t consist of any valid ascii character.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master bijective verification using simultaneous two-way mapping.
  • Implement position pattern matching without hash tables.
  • Handle all 256 ASCII characters safely.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Checking if two sequences have identical structural character templates.
  • Word pattern or isomorphism tests.

Algorithmic Decision Tree:

  • Bijective Character Mapping
  • Last Seen Index Pattern Matching

Connected Patterns:

Word PatternFind and Replace PatternGroup Shifted Strings

1. Two Hash Maps Bijective Mapping

Intuition

Maintain s2t and t2s hash maps. For index i from 0 to n - 1: let c1 = s[i] and c2 = t[i]. If c1 is in s2t and s2t[c1] != c2, return false. If c2 is in t2s and t2s[c2] != c1, return false. Otherwise, record s2t[c1] = c2 and t2s[c2] = c1. If all characters process without conflict, return true.

When to apply: The most clear explanation of the mathematical definition of bijection.

Algorithm

  1. Create two maps: mapS and mapT.
  2. Loop i from 0 to n - 1:
  3. If mapS.has(s[i]) and mapS.get(s[i]) != t[i], return false.
  4. If mapT.has(t[i]) and mapT.get(t[i]) != s[i], return false.
  5. Record mapS.set(s[i], t[i]) and mapT.set(t[i], s[i]).
  6. Return true.

Two Hash Maps Bijective Mapping Verification Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [e, g, g]
Current operationSTEP 1 OF 6
Observation: At index 0: s[0]='e' and t[0]='a'
Visual state
Values and pointers at this exact step
array
S
e
g
g
0
1
2
Variables at this step
mapST
{"e":"a"}
mapTS
{"a":"e"}
Valid
true
Check / comparison
s[0]='e', t[0]='a'. Check mapST['e'] and mapTS['a']. Neither exists.
Decision / next transition
Establish two-way mapping: mapST['e'] = 'a' and mapTS['a'] = 'e'.
Why this step matters

Observation: At index 0: s[0]='e' and t[0]='a'.

Decision: Neither character has been mapped yet. Set forward mapping 'e' -> 'a' and reverse mapping 'a' -> 'e'.

Invariant: Bijective 1-to-1 correspondence established for first character pair.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <unordered_map>
4
5class Solution {
6public:
7 bool isIsomorphic(std::string s, std::string t) {
8 if (s.size() != t.size()) return false;
9 std::unordered_map<char, char> s2t, t2s;
10
11 for (int i = 0; i < (int)s.size(); ++i) {
12 char c1 = s[i], c2 = t[i];
13 if (s2t.count(c1) && s2t[c1] != c2) return false;
14 if (t2s.count(c2) && t2s[c2] != c1) return false;
15 s2t[c1] = c2;
16 t2s[c2] = c1;
17 }
18 return true;
19 }
20};
21
22int main() {
23 Solution sol;
24 std::cout << (sol.isIsomorphic("egg", "add") ? "true" : "false") << std::endl; // true
25 std::cout << (sol.isIsomorphic("foo", "bar") ? "true" : "false") << std::endl; // false
26 return 0;
27}

Time & Space Complexity

  • Time complexity: O(N) — Single linear pass with constant-time hash map lookups.
  • Space complexity: O(K) where K <= 256 unique characters

Why Brute Force Doesn't Scale:

Two static 256-int arrays eliminate all hashing overhead.

Stack allocation of 512 integers has zero garbage collection overhead.

2. Single Hash Map with Visited Target Set

Intuition

Maintain a map mapping from character in s to character in t, and a set used of characters in t that have already been assigned. For each pair (s[i], t[i]): if s[i] is not in map, ensure t[i] is not in used (if it is, return false) and assign mapping[s[i]] = t[i], used.add(t[i]). If s[i] is already in map, verify mapping[s[i]] == t[i].

When to apply: Alternative formulation using map and set.

Algorithm

  1. Initialize map and usedSet.
  2. For each i from 0 to n - 1:
  3. If s[i] in map:
  4. If map[s[i]] != t[i], return false.
  5. Else:
  6. If t[i] in usedSet, return false.
  7. Set map[s[i]] = t[i] and usedSet.add(t[i]).
  8. Return true.

Single Hash Map with Visited Target Set Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [e, g, g]
Current operationSTEP 1 OF 6
Observation: Check index 0: s[0]='e', t[0]='a'
Visual state
Values and pointers at this exact step
array
S
e->a
0
↑ i=0 ('e','a')
Variables at this step
Map
{"e":"a"}
Used Set
["a"]
Valid
true
Check / comparison
map['e'] does not exist, and 'a' is not in usedTargets set.
Decision / next transition
Map 'e' -> 'a' and add 'a' to usedTargets set.
Why this step matters

Observation: Check index 0: s[0]='e', t[0]='a'.

Decision: 'e' is unmapped, and target 'a' has not been used. Map map['e'] = 'a' and usedTargets.add('a').

Invariant: Target 'a' is marked claimed.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <unordered_map>
4#include <unordered_set>
5
6class Solution {
7public:
8 bool isIsomorphic(std::string s, std::string t) {
9 std::unordered_map<char, char> map;
10 std::unordered_set<char> used;
11
12 for (int i = 0; i < (int)s.size(); ++i) {
13 char c1 = s[i], c2 = t[i];
14 if (map.count(c1)) {
15 if (map[c1] != c2) return false;
16 } else {
17 if (used.count(c2)) return false;
18 map[c1] = c2;
19 used.insert(c2);
20 }
21 }
22 return true;
23 }
24};
25
26int main() {
27 Solution sol;
28 std::cout << (sol.isIsomorphic("paper", "title") ? "true" : "false") << std::endl; // true
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(N) — Performs one pass over strings of length N.
  • Space complexity: O(K) where K <= 256

3. Last Seen Position Index Arrays (O(1) Space, Highest Speed)

Intuition

Initialize two integer arrays m1[256] and m2[256] with 0. Traverse both strings simultaneously: at index i, check m1[s[i]] and m2[t[i]]. If they differ, the characters appeared at different previous positions, violating isomorphism. Otherwise, update m1[s[i]] = i + 1 and m2[t[i]] = i + 1. (We use i + 1 so 0 denotes unvisited).

When to apply: Fastest execution without heap allocation or hash table overhead.

Algorithm

  1. Initialize int m1[256] = {0} and int m2[256] = {0}.
  2. Loop i from 0 to n - 1:
  3. If m1[(unsigned char)s[i]] != m2[(unsigned char)t[i]], return false.
  4. Set m1[(unsigned char)s[i]] = i + 1 and m2[(unsigned char)t[i]] = i + 1.
  5. Return true.

Bidirectional Character Projection Mapping

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [e, g, g]
Current operationSTEP 1 OF 6
Observation: At i = 0, s[0] = 'e' and t[0] = 'a'
Visual state
Values and pointers at this exact step
array
S
e
g
g
0
↑ i=0: 'e' <-> 'a'
1
2
Variables at this step
Index
0
s[0]
e
t[0]
a
mapST
{ e: 'a' }
mapTS
{ a: 'e' }
Check / comparison
Neither 'e' nor 'a' mapped. Establish map: 'e' -> 'a' and 'a' -> 'e'.
Decision / next transition
Valid bijection established for index 0.
Why this step matters

Observation: At i = 0, s[0] = 'e' and t[0] = 'a'. Neither character has been mapped.

Decision: Map mapST['e'] = 'a' and mapTS['a'] = 'e'.

Invariant: One-to-one character correspondence holds.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5public:
6 bool isIsomorphic(std::string s, std::string t) {
7 int m1[256] = {0};
8 int m2[256] = {0};
9 int n = s.size();
10
11 for (int i = 0; i < n; ++i) {
12 unsigned char c1 = s[i];
13 unsigned char c2 = t[i];
14 if (m1[c1] != m2[c2]) return false;
15 m1[c1] = i + 1;
16 m2[c2] = i + 1;
17 }
18 return true;
19 }
20};
21
22int main() {
23 Solution sol;
24 std::cout << (sol.isIsomorphic("egg", "add") ? "true" : "false") << std::endl; // true
25 std::cout << (sol.isIsomorphic("foo", "bar") ? "true" : "false") << std::endl; // false
26 std::cout << (sol.isIsomorphic("paper", "title") ? "true" : "false") << std::endl; // true
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(N) — Zero heap allocations, single pass of length N with direct array indexing.
  • Space complexity: O(1) strictly (two 256-int arrays on stack)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Two Hash Maps (Forward & Reverse)O(N)O(1) (ASCII character set)Extremely intuitive and clear bijection checking.Two hash map data structures.
2.Single Map + Visited SetO(N)O(1)One map and one set to prevent duplicate target mappings.Set lookup overhead.
3.Last Seen Position Arrays (Optimal)OptimalO(N)O(1) (two 256-int arrays)Zero dynamic memory allocations, maximum cache locality, fastest execution.Requires 1-based indexing trick.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Checking only single-direction mapping which allows many-to-one collisions.

Pitfall 2:

Using index 0 in integer array causing ambiguity with default uninitialized 0 (always use i + 1).

Crucial Edge Cases to Validate:

  • Two different characters map to same target (e.g. s="badc", t="baba"): At i=2, s[2]=d has last seen 0 but t[2]=b has last seen 1 (from i=0), discrepancy triggers immediate false.
  • Character maps to itself (e.g. s=a, t=a): Both m1[a] and m2[a] update synchronously, returning true.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always clarify if the string is ASCII or Unicode.
  2. Explain why a two-way mapping is necessary rather than a single map.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why do we record i + 1 instead of i in the last seen array?

Back to DSA Sheet