Isomorphic Strings

🎯

Isomorphic Strings

easyHASH_MAPAmazonLinkedInFacebook

Imagine you want to check if two words can be transformed into each other by consistently replacing characters, like a secret code where each letter maps uniquely to another.

💡 This problem tests your understanding of mapping relationships between characters in two strings. Beginners often struggle because they forget to ensure the mapping is one-to-one and onto, leading to incorrect assumptions about character replacements.

📋

Problem Statement

Given two strings s and t, determine if they are isomorphic. Two strings are isomorphic if the characters in s can be replaced to get t, with each character mapping to exactly one other character and no two characters mapping to the same character.

1 ≤ length of s, t ≤ 10^5s and t consist of any valid ASCII characters

💡

Example

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

Outputtrue

e maps to a, g maps to d, consistent mapping

Input"s = \"foo\", t = \"bar\""

Outputfalse

o cannot map to both a and r

Input"s = \"paper\", t = \"title\""

Outputtrue

p→t, a→i, e→l, r→e mapping works

• Empty strings s = "", t = "" → true
• Strings of different lengths s = "abc", t = "de" → false
• Strings with repeated characters but different patterns s = "ab", t = "aa" → false
• Strings with all characters the same s = "aaa", t = "bbb" → true

⚠️

Common Mistakes

Checking only s->t mapping without verifying t->s

Incorrectly returns true for inputs like s="ab", t="aa"

✅ Add reverse mapping check from t to s

Not checking length equality before processing

May cause index errors or incorrect true result

✅ Add length check at start

Using nested loops for large inputs

Time limit exceeded or slow performance

✅ Use hash maps for linear time solution

Assuming characters are only alphabets

Fails on inputs with digits or symbols

✅ Use generic hash maps that support all characters

🧠

Brute Force (Nested Loops Checking All Mappings)

💡 This approach exists to build intuition by explicitly checking every possible character mapping, even though it's inefficient. It helps beginners understand the problem's core requirement of consistent character replacement.

Intuition

Try every possible mapping from characters in s to characters in t by checking all pairs and verifying consistency.

Algorithm

1. For each character in s, try to map it to a character in t.
2. Check if this mapping is consistent throughout the strings.
3. If any inconsistency is found, return false.
4. If all characters map consistently, return true.

💡 This algorithm is straightforward but inefficient because it tries to verify mappings repeatedly without storing results.

</>

Code

def isIsomorphic(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    for i in range(len(s)):
        for j in range(len(s)):
            if (s[i] == s[j]) != (t[i] == t[j]):
                return False
    return True

# Driver code
if __name__ == "__main__":
    print(isIsomorphic("egg", "add"))  # True
    print(isIsomorphic("foo", "bar"))  # False
    print(isIsomorphic("paper", "title"))  # True

Line Notes

if len(s) != len(t):Quickly eliminate strings of different lengths which cannot be isomorphic

for i in range(len(s))Outer loop picks first character index to compare

for j in range(len(s))Inner loop compares with every other character index

if (s[i] == s[j]) != (t[i] == t[j]):Check if character equality in s matches equality in t; mismatch means not isomorphic

public class Solution {
    public static boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) return false;
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < s.length(); j++) {
                if ((s.charAt(i) == s.charAt(j)) != (t.charAt(i) == t.charAt(j))) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isIsomorphic("egg", "add")); // true
        System.out.println(isIsomorphic("foo", "bar")); // false
        System.out.println(isIsomorphic("paper", "title")); // true
    }
}

Line Notes

if (s.length() != t.length())Eliminate strings of different lengths early

for (int i = 0; i < s.length(); i++)Outer loop selects first character index

for (int j = 0; j < s.length(); j++)Inner loop compares with all other indices

if ((s.charAt(i) == s.charAt(j)) != (t.charAt(i) == t.charAt(j)))Check if equality pattern matches between s and t

#include <iostream>
#include <string>
using namespace std;

bool isIsomorphic(string s, string t) {
    if (s.length() != t.length()) return false;
    for (int i = 0; i < s.length(); i++) {
        for (int j = 0; j < s.length(); j++) {
            if ((s[i] == s[j]) != (t[i] == t[j])) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    cout << boolalpha << isIsomorphic("egg", "add") << endl; // true
    cout << boolalpha << isIsomorphic("foo", "bar") << endl; // false
    cout << boolalpha << isIsomorphic("paper", "title") << endl; // true
    return 0;
}

Line Notes

if (s.length() != t.length())Quick length check to avoid unnecessary computation

for (int i = 0; i < s.length(); i++)Outer loop picks character index i

for (int j = 0; j < s.length(); j++)Inner loop picks character index j for comparison

if ((s[i] == s[j]) != (t[i] == t[j]))Mismatch in equality pattern means strings are not isomorphic

function isIsomorphic(s, t) {
    if (s.length !== t.length) return false;
    for (let i = 0; i < s.length; i++) {
        for (let j = 0; j < s.length; j++) {
            if ((s[i] === s[j]) !== (t[i] === t[j])) {
                return false;
            }
        }
    }
    return true;
}

// Test cases
console.log(isIsomorphic("egg", "add")); // true
console.log(isIsomorphic("foo", "bar")); // false
console.log(isIsomorphic("paper", "title")); // true

Line Notes

if (s.length !== t.length)Eliminate strings of different lengths immediately

for (let i = 0; i < s.length; i++)Outer loop selects index i

for (let j = 0; j < s.length; j++)Inner loop selects index j for pairwise comparison

if ((s[i] === s[j]) !== (t[i] === t[j]))Check if equality relation between characters matches in both strings

⏱

Complexity

TimeO(n^2)

SpaceO(1)

Two nested loops each run n times, checking all pairs of characters

💡 For n=1000, this means about 1,000,000 comparisons, which is slow for large inputs

Interview Verdict: Use only to introduce - too slow for large inputs

This approach is correct but inefficient; it helps understand the problem but is not practical for interviews.

🧠

Hash Map with Single Direction Mapping

💡 This approach introduces hash maps to store character mappings from s to t, improving efficiency by avoiding repeated comparisons.

Intuition

Map each character in s to a character in t as you iterate, ensuring no conflicting mappings occur.

Algorithm

1. If lengths differ, return false immediately.
2. Create a hash map to store mappings from characters in s to characters in t.
3. Iterate through characters of s and t simultaneously.
4. For each character pair, check if mapping exists and is consistent; if not, return false.
5. If no conflicts, return true.

💡 This algorithm is easier to implement and faster than brute force but misses checking if two characters in s map to the same character in t.

</>

Code

def isIsomorphic(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    mapping = {}
    for c1, c2 in zip(s, t):
        if c1 in mapping:
            if mapping[c1] != c2:
                return False
        else:
            mapping[c1] = c2
    return True

# Driver code
if __name__ == "__main__":
    print(isIsomorphic("egg", "add"))  # True
    print(isIsomorphic("foo", "bar"))  # False
    print(isIsomorphic("paper", "title"))  # True

Line Notes

if len(s) != len(t):Early exit for strings of different lengths

mapping = {}Initialize dictionary to store s->t character mappings

for c1, c2 in zip(s, t):Iterate over paired characters from s and t

if c1 in mapping:Check if current s character already has a mapped t character

import java.util.*;
public class Solution {
    public static boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) return false;
        Map<Character, Character> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c1 = s.charAt(i), c2 = t.charAt(i);
            if (map.containsKey(c1)) {
                if (map.get(c1) != c2) return false;
            } else {
                map.put(c1, c2);
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isIsomorphic("egg", "add")); // true
        System.out.println(isIsomorphic("foo", "bar")); // false
        System.out.println(isIsomorphic("paper", "title")); // true
    }
}

Line Notes

if (s.length() != t.length())Check length mismatch early

Map<Character, Character> map = new HashMap<>();Create map for s->t character mapping

for (int i = 0; i < s.length(); i++)Iterate over characters by index

if (map.containsKey(c1))Check if s character already mapped

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

bool isIsomorphic(string s, string t) {
    if (s.length() != t.length()) return false;
    unordered_map<char, char> map;
    for (int i = 0; i < s.length(); i++) {
        char c1 = s[i], c2 = t[i];
        if (map.count(c1)) {
            if (map[c1] != c2) return false;
        } else {
            map[c1] = c2;
        }
    }
    return true;
}

int main() {
    cout << boolalpha << isIsomorphic("egg", "add") << endl; // true
    cout << boolalpha << isIsomorphic("foo", "bar") << endl; // false
    cout << boolalpha << isIsomorphic("paper", "title") << endl; // true
    return 0;
}

Line Notes

if (s.length() != t.length())Length check to avoid unnecessary work

unordered_map<char, char> map;Map to store s->t character mappings

for (int i = 0; i < s.length(); i++)Iterate through characters by index

if (map.count(c1))Check if mapping for s character exists

function isIsomorphic(s, t) {
    if (s.length !== t.length) return false;
    const map = new Map();
    for (let i = 0; i < s.length; i++) {
        const c1 = s[i], c2 = t[i];
        if (map.has(c1)) {
            if (map.get(c1) !== c2) return false;
        } else {
            map.set(c1, c2);
        }
    }
    return true;
}

// Test cases
console.log(isIsomorphic("egg", "add")); // true
console.log(isIsomorphic("foo", "bar")); // false
console.log(isIsomorphic("paper", "title")); // true

Line Notes

if (s.length !== t.length)Early exit for length mismatch

const map = new Map();Create map for s->t character mapping

for (let i = 0; i < s.length; i++)Iterate over indices

if (map.has(c1))Check if s character already mapped

⏱

Complexity

TimeO(n)

SpaceO(n)

Single pass through strings with constant-time map operations

💡 For n=1000, this means about 1000 operations, much faster than brute force

Interview Verdict: Accepted but incomplete - misses reverse mapping check

This approach is efficient but can fail if two characters in s map to the same character in t, which is invalid.

🧠

Optimal Bidirectional Hash Map Mapping

💡 This approach ensures a one-to-one mapping by maintaining two hash maps, one from s to t and another from t to s, guaranteeing no two characters map to the same character.

Intuition

Track mappings in both directions simultaneously to ensure uniqueness and consistency.

Algorithm

1. If lengths differ, return false immediately.
2. Create two hash maps: s_to_t and t_to_s.
3. Iterate through characters of s and t simultaneously.
4. For each pair, check if mappings exist and are consistent in both maps.
5. If any inconsistency is found, return false.
6. If all pairs are consistent, return true.

💡 This algorithm is the most robust and efficient, ensuring no conflicting mappings in either direction.

</>

Code

def isIsomorphic(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    s_to_t = {}
    t_to_s = {}
    for c1, c2 in zip(s, t):
        if c1 in s_to_t:
            if s_to_t[c1] != c2:
                return False
        else:
            s_to_t[c1] = c2
        if c2 in t_to_s:
            if t_to_s[c2] != c1:
                return False
        else:
            t_to_s[c2] = c1
    return True

# Driver code
if __name__ == "__main__":
    print(isIsomorphic("egg", "add"))  # True
    print(isIsomorphic("foo", "bar"))  # False
    print(isIsomorphic("paper", "title"))  # True
    print(isIsomorphic("ab", "aa"))  # False

Line Notes

if len(s) != len(t):Early exit for length mismatch

s_to_t = {}Map from s characters to t characters

t_to_s = {}Map from t characters to s characters

if c1 in s_to_t:Check existing mapping from s to t for consistency

import java.util.*;
public class Solution {
    public static boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) return false;
        Map<Character, Character> sToT = new HashMap<>();
        Map<Character, Character> tToS = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c1 = s.charAt(i), c2 = t.charAt(i);
            if (sToT.containsKey(c1)) {
                if (sToT.get(c1) != c2) return false;
            } else {
                sToT.put(c1, c2);
            }
            if (tToS.containsKey(c2)) {
                if (tToS.get(c2) != c1) return false;
            } else {
                tToS.put(c2, c1);
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isIsomorphic("egg", "add")); // true
        System.out.println(isIsomorphic("foo", "bar")); // false
        System.out.println(isIsomorphic("paper", "title")); // true
        System.out.println(isIsomorphic("ab", "aa")); // false
    }
}

Line Notes

if (s.length() != t.length())Length check to avoid unnecessary processing

Map<Character, Character> sToT = new HashMap<>();Map s->t characters

Map<Character, Character> tToS = new HashMap<>();Map t->s characters

if (sToT.containsKey(c1))Check if s character already mapped to a consistent t character

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

bool isIsomorphic(string s, string t) {
    if (s.length() != t.length()) return false;
    unordered_map<char, char> sToT, tToS;
    for (int i = 0; i < s.length(); i++) {
        char c1 = s[i], c2 = t[i];
        if (sToT.count(c1)) {
            if (sToT[c1] != c2) return false;
        } else {
            sToT[c1] = c2;
        }
        if (tToS.count(c2)) {
            if (tToS[c2] != c1) return false;
        } else {
            tToS[c2] = c1;
        }
    }
    return true;
}

int main() {
    cout << boolalpha << isIsomorphic("egg", "add") << endl; // true
    cout << boolalpha << isIsomorphic("foo", "bar") << endl; // false
    cout << boolalpha << isIsomorphic("paper", "title") << endl; // true
    cout << boolalpha << isIsomorphic("ab", "aa") << endl; // false
    return 0;
}

Line Notes

if (s.length() != t.length())Length mismatch check

unordered_map<char, char> sToT, tToS;Two maps for bidirectional character mapping

if (sToT.count(c1))Check if s character already mapped to a consistent t character

if (tToS.count(c2))Check if t character already mapped to a consistent s character

function isIsomorphic(s, t) {
    if (s.length !== t.length) return false;
    const sToT = new Map();
    const tToS = new Map();
    for (let i = 0; i < s.length; i++) {
        const c1 = s[i], c2 = t[i];
        if (sToT.has(c1)) {
            if (sToT.get(c1) !== c2) return false;
        } else {
            sToT.set(c1, c2);
        }
        if (tToS.has(c2)) {
            if (tToS.get(c2) !== c1) return false;
        } else {
            tToS.set(c2, c1);
        }
    }
    return true;
}

// Test cases
console.log(isIsomorphic("egg", "add")); // true
console.log(isIsomorphic("foo", "bar")); // false
console.log(isIsomorphic("paper", "title")); // true
console.log(isIsomorphic("ab", "aa")); // false

Line Notes

if (s.length !== t.length)Early exit for length mismatch

const sToT = new Map();Map s->t characters

const tToS = new Map();Map t->s characters

if (sToT.has(c1))Check if s character already mapped to consistent t character

⏱

Complexity

TimeO(n)

SpaceO(n)

Single pass with constant-time map lookups and insertions

💡 For n=1000, this approach performs about 1000 operations, efficient for large inputs

Interview Verdict: Accepted - optimal solution

This approach is the best balance of correctness and efficiency, suitable for interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 Use the optimal bidirectional hash map approach in 95% of interviews for correctness and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code
2. Single Direction Hash Map	O(n)	O(n)	No	N/A	Mention as intermediate step, explain flaw
3. Bidirectional Hash Map (Optimal)	O(n)	O(n)	No	N/A	Code this approach

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding each approach, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify problem constraints and examples.Step 2: Describe brute force approach to show understanding.Step 3: Introduce hash map for one-direction mapping and discuss its flaw.Step 4: Present optimal bidirectional mapping solution.Step 5: Code the optimal solution and test edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Interviewer tests your ability to identify one-to-one character mappings, handle edge cases, and optimize from naive to efficient solutions.

Common Follow-ups

• What if strings contain Unicode characters? → Use hash maps that support Unicode keys.
• Can you solve this without extra space? → Not efficiently; mapping requires storage.

💡 Follow-ups often test your understanding of character sets and space-time tradeoffs.

🔍

Pattern Recognition

When to Use

1) Need to check character-by-character mapping consistency, 2) One-to-one mapping required, 3) Strings of equal length, 4) Hash maps or sets can track mappings

Signature Phrases

characters can be replacedone-to-one mappingconsistent mapping

NOT This Pattern When

Problems that require substring matching or anagrams are different patterns.

Similar Problems

Word Pattern - similar character pattern matchingIsomorphic Words - variant with word tokens instead of characters

Practice

1. Given the following code, what is the return value when the input string is "aabc"?

easy

A. 2

B. 1

C. -1

D. 0

Solution

1. Step 1: Trace frequency and first_index dictionaries

   For "aabc": freq={'a':2, 'b':1, 'c':1}, first_index={'a':0, 'b':2, 'c':3}

2. Step 2: Find minimum index with frequency 1

   Characters with count 1 are 'b' at index 2 and 'c' at index 3; minimum is 2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   First unique char is 'b' at index 2 [OK]

Hint: Check frequency and first occurrence carefully [OK]

Common Mistakes:

• Returning character instead of index
• Off-by-one index errors
• Ignoring multiple unique chars

2. You need to design a data structure that supports inserting elements, deleting elements, and retrieving a random element, all in average constant time. Which approach best guarantees this performance?

easy

A. Using a balanced binary search tree to maintain elements and their indices

B. Combining a hash map for element indices with an array to store elements, using a swap-delete trick on removal

C. Using a linked list for elements and a hash set for membership checks

D. Maintaining a sorted array and performing binary search for insertions and deletions

Solution

1. Step 1: Understand operation requirements

   Insert, delete, and getRandom must all be O(1) average time.

2. Step 2: Evaluate data structures

   Balanced BST or sorted array have O(log n) or worse for insert/delete. Linked list lacks O(1) random access. Hash map + array with swap-delete achieves O(1) for all operations.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Hash map + array with swap-delete is the classic O(1) solution [OK]

Hint: Hash map + array with swap-delete enables O(1) ops [OK]

Common Mistakes:

• Thinking balanced BST gives O(1) insert/delete
• Using linked list for O(1) random access
• Assuming sorted array can do O(1) insert/delete

3. The following code attempts to detect a continuous subarray sum divisible by k. Which line contains a subtle bug that can cause incorrect results on some inputs?

medium

A. Line 7: normalizing k if negative

B. Line 9: computing total modulo k without handling negative values

C. Line 3: initializing remainder_map with {0: -1}

D. Line 12: checking if subarray length > 1

Solution

1. Step 1: Identify modulo operation on line 9

   The code uses total = total % k without adjusting for negative totals, which can yield negative remainders.

2. Step 2: Understand impact of negative remainders

   Negative remainders cause incorrect remainder_map keys, missing valid subarrays.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Modulo must be normalized to non-negative remainder [OK]

Hint: Modulo with negatives must be normalized to positive remainder [OK]

Common Mistakes:

• Not normalizing modulo results for negative sums
• Overwriting remainder_map entries instead of preserving earliest index
• Allowing subarrays of length 1 to return True

4. What is the time complexity of the optimal hash set approach for finding the longest consecutive sequence in an array of size n?

medium

A. O(n log n) due to sorting inside the algorithm

B. O(n) because each number is processed at most twice

C. O(n²) because of nested loops checking consecutive numbers

D. O(n) average but O(n²) worst case due to hash collisions

Solution

1. Step 1: Analyze outer loop

   The outer loop iterates over each unique number once.

2. Step 2: Analyze inner while loop

   Each number is visited at most once in the inner loop when counting consecutive sequences, so total work is O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Hash set lookups are O(1), total linear time [OK]

Hint: Each element visited once in sequence counting [OK]

Common Mistakes:

• Assuming sorting is involved causing O(n log n)
• Confusing nested loops as O(n²)
• Overestimating hash collision impact

5. Suppose the problem is modified so that characters can be reused multiple times and you want to find the first unique character index after removing all duplicates. Which modification to the optimal approach correctly handles this variant?

hard

A. Sort the string and pick the first character that appears once, ignoring original indices.

B. Use a queue to track characters as they appear and remove duplicates dynamically during iteration.

C. Use the same frequency map approach but only consider characters with frequency exactly one after removal.

D. Use a brute force nested loop to check uniqueness after each removal.

Solution

1. Step 1: Understand the reuse and removal requirement

   Characters can be reused, so duplicates must be removed dynamically to find first unique.

2. Step 2: Identify approach that dynamically tracks uniqueness

   A queue can track order and remove duplicates as they appear, maintaining first unique efficiently.

3. Step 3: Evaluate other options

   Sorting loses original order; brute force is inefficient; frequency map alone can't handle dynamic removals.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Queue-based approach handles dynamic uniqueness correctly [OK]

Hint: Dynamic uniqueness needs a queue, not just frequency map [OK]

Common Mistakes:

• Assuming static frequency map suffices
• Sorting loses original order
• Brute force is too slow