Isomorphic Strings

Difficulty: Easy
Topics: Hash Table, String
Link: https://leetcode.com/problems/isomorphic-strings/

Problem 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.

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:

Input: s = “egg”, t = “add”

Output: true

Explanation:

The strings s and t can be made identical by:

Mapping 'e' to 'a'.
Mapping 'g' to 'd'.

Example 2:

Input: s = “foo”, t = “bar”

Output: false

Explanation:

The strings s and t can not be made identical as 'o' needs to be mapped to both 'a' and 'r'.

Example 3:

Input: s = “paper”, t = “title”

Output: true

Constraints:

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

Solution

1. Problem Deconstruction

Technical Restatement
Given two strings s and t of equal length $n$ , determine if there exists a bijective mapping $f: \Sigma_s \rightarrow \Sigma_t$ between their character sets such that for every index $i \in [0, n-1]$ , $f(s[i]) = t[i]$ . The mapping must satisfy:

Injective: $\forall c_1, c_2 \in \Sigma_s, f(c_1) = f(c_2) \Rightarrow c_1 = c_2$
Surjective: $\forall d \in \Sigma_t, \exists c \in \Sigma_s$ such that $f(c) = d$
Position-preserving: The mapping applies uniformly across all occurrences

Beginner-Friendly Explanation
Imagine you have two words written in secret codes. You want to check if you can create a consistent substitution cipher between them. Every time a letter appears in the first word, it must always translate to the same letter in the second word. Also, no two different letters from the first word can translate to the same letter in the second word.

Mathematical Formulation
Let $s = s_0s_1...s_{n-1}$ and $t = t_0t_1...t_{n-1}$ be strings of length $n$ .
They are isomorphic if there exists a bijection $f: \text{chars}(s) \rightarrow \text{chars}(t)$ such that:

f(s_i) = t_i \quad \forall i \in [0, n-1]

Equivalently, for all indices $i, j$ :

s_i = s_j \iff t_i = t_j

and

s_i \neq s_j \iff t_i \neq t_j

Constraint Analysis

Length constraint: $1 \leq n \leq 5 \times 10^4$
Implication: $O(n^2)$ solutions are infeasible (~ $2.5 \times 10^9$ operations). Need $O(n)$ or $O(n \log n)$ .
Equal length: $|s| = |t|$
Implication: No need to handle length mismatch edge case
ASCII characters: Any valid ASCII (0-127 or 0-255)
Implication: Can use fixed-size arrays for mapping rather than hash maps Edge case: Non-printable characters possible but rare
Empty string: Minimum length 1 eliminates empty string consideration

2. Intuition Scaffolding

Real-World Metaphor: Language Translation Consistency
Imagine translating an English document to French. If the word “the” always translates to “le”, this consistency must hold throughout. You cannot have “the” sometimes becoming “la”. Also, two different English words cannot both translate to the same French word.

Gaming Analogy: Character Skin Mapping
In a game where characters can wear different skins, if player A chooses “Mage” skin and player B sees them as “Wizard”, this mapping must be consistent for all Mage appearances. No two different base characters can share the same visible skin for any observer.

Math Analogy: Graph Isomorphism
Consider each string as a graph where characters are nodes and positions define edges to subsequent characters. Isomorphism requires that the adjacency structure is preserved under a consistent vertex relabeling.

Common Pitfalls

Unidirectional mapping only: Checking $s \rightarrow t$ but forgetting $t \rightarrow s$ constraints
Position-independent counting: Assuming character frequency matching is sufficient
First-occurrence mapping: Only checking the first instance of each character
Over-optimization: Using arrays without considering character set size
Late validation: Building full mapping before checking conflicts

3. Approach Encyclopedia

Brute Force Approach
Check all possible character mappings through exhaustive comparison.

def isIsomorphic_brute(s: str, t: str) -> bool:
    n = len(s)
    
    # Check every position against all others
    for i in range(n):
        for j in range(i + 1, n):
            # If characters in s match but corresponding t characters don't
            if s[i] == s[j] and t[i] != t[j]:
                return False
            # If characters in s don't match but corresponding t characters do
            if s[i] != s[j] and t[i] == t[j]:
                return False
    return True

Complexity Proof

Time: $O(n^2)$ from nested loops $\sum_{i=0}^{n-1} \sum_{j=i+1}^{n-1} 1 = \frac{n(n-1)}{2} \in \Theta(n^2)$
Space: $O(1)$ excluding input storage

Visualization

s: e g g
   | | |
t: a d d

i=0, j=1: e≠g, a≠d ✓
i=0, j=2: e≠g, a≠d ✓  
i=1, j=2: g=g, d=d ✓
All checks pass → True

Hash Map Approach (Dual Mapping)

def isIsomorphic_hash(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    
    s_to_t = {}  # Mapping from s chars to t chars
    t_to_s = {}  # Mapping from t chars to s chars
    
    for cs, ct in zip(s, t):
        # Check forward mapping consistency
        if cs in s_to_t:
            if s_to_t[cs] != ct:
                return False
        else:
            s_to_t[cs] = ct
        
        # Check reverse mapping consistency  
        if ct in t_to_s:
            if t_to_s[ct] != cs:
                return False
        else:
            t_to_s[ct] = cs
    
    return True

Complexity Proof

Time: $O(n)$ where $n$ is string length. Each character processed once with $O(1)$ hash operations
Space: $O(|\Sigma|)$ where $\Sigma$ is character set. Worst case $O(min(n, 128))$ for ASCII

Visualization

Step 0: s_to_t={}, t_to_s={}
e→a: s_to_t={'e':'a'}, t_to_s={'a':'e'}
g→d: s_to_t={'e':'a','g':'d'}, t_to_s={'a':'e','d':'g'}  
g→d: Consistent with existing mapping ✓

Array-Based Approach (Optimal)

def isIsomorphic_optimal(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    
    # ASCII extended range (0-255)
    s_map = [-1] * 256  # Track last seen position for s chars
    t_map = [-1] * 256  # Track last seen position for t chars
    
    for i in range(len(s)):
        cs, ct = s[i], t[i]
        # Convert to integer index
        idx_s, idx_t = ord(cs), ord(ct)
        
        # Check if characters were last mapped at different positions
        if s_map[idx_s] != t_map[idx_t]:
            return False
        
        # Update both mappings with current position
        s_map[idx_s] = t_map[idx_t] = i
    
    return True

Complexity Proof

Time: $O(n)$ - single pass with constant-time array operations
Space: $O(1)$ - fixed 256-element arrays regardless of input size

Visualization

s: e g g, t: a d d
i=0: s_map['e']=-1, t_map['a']=-1 → match
     Update both to 0
i=1: s_map['g']=-1, t_map['d']=-1 → match  
     Update both to 1
i=2: s_map['g']=1, t_map['d']=1 → match
     Update both to 2
All match → True

4. Code Deep Dive

Optimal Solution Annotation

def isIsomorphic(s: str, t: str) -> bool:
    # Early validation of equal length
    if len(s) != len(t):
        return False
    
    # Initialize mapping arrays for extended ASCII
    # Using -1 as "unmapped" sentinel value
    s_map = [-1] * 256  # Tracks last position of each s character
    t_map = [-1] * 256  # Tracks last position of each t character
    
    for i in range(len(s)):
        # Get current character pair and convert to indices
        cs, ct = s[i], t[i]
        idx_s, idx_t = ord(cs), ord(ct)
        
        # Core isomorphism check:
        # If the last seen positions don't match, mapping is inconsistent
        # This simultaneously validates both directional constraints
        if s_map[idx_s] != t_map[idx_t]:
            return False
        
        # Update both mappings with current position index
        # This records that these characters were last seen together at position i
        s_map[idx_s] = i
        t_map[idx_t] = i
    
    # All character pairs passed consistency check
    return True

Edge Case Handling

Example 1 ("egg", "add"):
Line 12 never triggers return False as positions stay synchronized
Example 2 ("foo", "bar"):
At i=2: s_map['o']=1 but t_map['r']=-1 → inequality detected
Example 3 ("paper", "title"):
All character pairs maintain position synchronization
Self-mapping ("abc", "abc"):
Identity mapping works as positions remain equal
Non-printable ASCII: Ordinal conversion handles all 0-255 values

5. Complexity War Room

Hardware-Aware Analysis

Memory: 256 × 2 arrays × 4 bytes/int ≈ 2KB, fits comfortably in L1 cache
Processing: Single pass with 5-6 operations per character, ~250K ops for max input
Cache performance: Sequential array access enables prefetching and vectorization

Industry Comparison Table

Approach	Time	Space	Readability	Interview Viability
Brute Force	$O(n^2)$	$O(1)$	10/10	❌ Fails large N
Single HashMap	$O(n)$	$O(	\Sigma	)$
Dual HashMap	$O(n)$	$O(	\Sigma	)$
Array Mapping	$O(n)$	$O(1)$	7/10	✅ Optimal choice

6. Pro Mode Extras

Variants & Extensions

K-Isomorphic Strings: Allow up to K mapping inconsistencies
Group Isomorphism: Check if strings are isomorphic to any in a set
Approximate Isomorphism: Find mapping that minimizes mismatches
LC 205 Follow-up: What if we allow multiple transactions? (Not applicable - single mapping)

Interview Cheat Sheet

First Mention: Always state time/space complexity upfront
Clarification: Ask about character set (Unicode vs ASCII)
Progression: Start with brute force, then hash map, then optimal
Testing: Include bidirectional violation cases in examples
Optimization: Mention cache locality benefits of array approach

Mathematical Insight
The position-tracking solution leverages the equivalence:

s \cong t \iff \forall i,j: \text{lastPos}(s[i]) = \text{lastPos}(t[i])

where lastPos© is the most recent occurrence index of character c. This elegantly encodes both injectivity and surjectivity constraints in a single equality check.

#205 - Isomorphic Strings

Isomorphic Strings

Problem Description

Solution

1. Problem Deconstruction

2. Intuition Scaffolding

3. Approach Encyclopedia

4. Code Deep Dive

5. Complexity War Room

6. Pro Mode Extras