Isomorphic Strings

📋

Problem

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.

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

Edge cases: Empty strings s = "", t = "" → trueStrings of different lengths s = "abc", t = "de" → falseStrings with repeated characters but different patterns s = "ab", t = "aa" → false

</>

IDE

def isIsomorphic(s: str, t: str) -> bool:public boolean isIsomorphic(String s, String t)bool isIsomorphic(string s, string t)function isIsomorphic(s, t)

def isIsomorphic(s, t):
    # Write your solution here
    pass

class Solution {
    public boolean isIsomorphic(String s, String t) {
        // Write your solution here
        return false;
    }
}

#include <string>
using namespace std;

bool isIsomorphic(string s, string t) {
    // Write your solution here
    return false;
}

function isIsomorphic(s, t) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: trueFails to check that two different characters in s map to the same character in t✅ Add reverse mapping from t to s and verify no duplicates before returning true

Wrong: falseIncorrectly returns false on empty strings or single character strings✅ Add base case checks for empty strings and single character strings returning true

Wrong: trueFails to check string length equality before mapping✅ Add length equality check at start and return false if lengths differ

Wrong: trueGreedy mapping assigns multiple characters in s to same character in t without validation✅ Use bidirectional maps and check consistency for all character pairs

Wrong: TLEUses nested loops causing O(n^2) time complexity on large inputs✅ Implement O(n) solution using hash maps for character mapping

✓

Test Cases

Focus on handling empty and minimal inputs correctly before moving on.

Ensure your mapping logic is bidirectional and consistent for all characters.

Optimize your solution to linear time to handle large inputs efficiently.

t1_01basic

Input{"s":"egg","t":"add"}

Expectedtrue

⏱ Performance - must finish in 2000ms

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

💡 Check if each character in s consistently maps to one character in t

💡 Use a hash map to track character mappings from s to t and verify no conflicts

💡 Ensure no two characters in s map to the same character in t by checking reverse mapping

Why it failed: Returned false or inconsistent mapping detected; fix by maintaining bidirectional maps to ensure one-to-one character mapping.

✓ Correctly identified consistent character mapping.

t1_02basic

Input{"s":"paper","t":"title"}

Expectedtrue

⏱ Performance - must finish in 2000ms

p maps to t, a maps to i, e maps to l, r maps to e; all consistent

💡 Verify character mapping consistency across entire strings

💡 Check both forward and backward mappings to avoid duplicates

💡 Use two hash maps or sets to track mappings from s to t and t to s

Why it failed: Failed to check reverse mapping causing multiple s chars mapping to same t char; fix by adding reverse map validation.

✓ Correctly handled bidirectional mapping for isomorphism.

t2_01edge

Input{"s":"","t":""}

Expectedtrue

⏱ Performance - must finish in 2000ms

Empty strings are trivially isomorphic

💡 Consider what happens when input strings are empty

💡 Check if your code handles zero-length inputs without errors

💡 Return true immediately if both strings are empty

Why it failed: Code crashes or returns false on empty strings; fix by adding base case for empty inputs.

✓ Correctly handles empty string inputs.

t2_02edge

Input{"s":"a","t":"b"}

Expectedtrue

⏱ Performance - must finish in 2000ms

Single character strings map trivially

💡 Test with minimal input size of one character

💡 Ensure mapping logic works for single character pairs

💡 Return true if lengths are equal and single chars map uniquely

Why it failed: Fails single character case by overcomplicating mapping; fix by handling single char mapping correctly.

✓ Correctly handles single character strings.

t2_03edge

Input{"s":"abc","t":"de"}

Expectedfalse

⏱ Performance - must finish in 2000ms

Strings of different lengths cannot be isomorphic

💡 Check if string lengths differ before mapping

💡 Return false immediately if lengths are not equal

💡 Add length check at start to optimize and avoid unnecessary processing

Why it failed: Fails to check length equality causing incorrect true; fix by adding length equality check at start.

✓ Correctly rejects strings of different lengths.

t3_01corner

Input{"s":"ab","t":"aa"}

Expectedfalse

⏱ Performance - must finish in 2000ms

Different characters in s map to same character in t, violating one-to-one mapping

💡 Check if multiple characters in s map to the same character in t

💡 Maintain reverse mapping from t to s to detect duplicates

💡 Return false if a character in t is already mapped to a different character in s

Why it failed: Missed reverse mapping check allowing multiple s chars to map to same t char; fix by adding reverse map validation.

✓ Correctly detects violation of one-to-one mapping.

t3_02corner

Input{"s":"aaa","t":"bbb"}

Expectedtrue

⏱ Performance - must finish in 2000ms

All characters in s map to the same character in t consistently

💡 Verify that repeated characters map consistently to same character

💡 Check that mapping does not change for repeated characters

💡 Ensure mapping is consistent for all occurrences of a character

Why it failed: Fails to handle repeated characters mapping consistently; fix by checking mapping consistency for repeated chars.

✓ Correctly handles repeated characters mapping.

t3_03corner

Input{"s":"foo","t":"bar"}

Expectedfalse

⏱ Performance - must finish in 2000ms

Greedy approach fails because 'o' maps to two different characters

💡 Beware of greedy mapping that assigns characters without checking consistency

💡 Check all character pairs for consistent mapping, not just first occurrences

💡 Use bidirectional maps to ensure no conflicting mappings

Why it failed: Greedy mapping assigns 'o' to both 'a' and 'r'; fix by verifying mapping consistency for all positions.

✓ Correctly rejects inconsistent mappings caught by greedy trap.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

n=100000, O(n) solution must complete within 2 seconds

💡 Use O(n) time complexity approach with hash maps

💡 Avoid nested loops that cause O(n^2) time

💡 Implement bidirectional mapping with constant time lookups

Why it failed: TLE due to O(n^2) brute force approach; fix by using O(n) hash map based solution.

✓ Efficient O(n) solution confirmed by passing performance test.

Practice

1. You are given a positive integer and need to determine if repeatedly replacing the number by the sum of the squares of its digits eventually leads to 1 or falls into a repeating cycle. Which approach guarantees an optimal solution with constant space and known cycle detection?

easy

A. Use a mathematical insight with a known set of cycle numbers to detect unhappy cycles

B. Use a greedy approach that picks the largest digit's square sum at each step

C. Use dynamic programming to store intermediate sums and avoid recomputation

D. Use brute force with a hash set to detect cycles by storing all seen numbers

Solution

1. Step 1: Understand the problem pattern

   The problem requires detecting if a number eventually reaches 1 or cycles indefinitely by repeatedly summing squares of digits.

2. Step 2: Identify the optimal approach

   Using a known set of unhappy cycle numbers allows constant space cycle detection, avoiding overhead of storing all seen numbers.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Known cycle detection uses constant space and is optimal [OK]

Hint: Known unhappy cycles enable constant space detection [OK]

Common Mistakes:

• Assuming greedy or DP approaches solve cycle detection optimally

2. You are given two strings and need to determine if one is a rearrangement of the other, meaning they contain the same characters with the same frequency. Which approach guarantees an optimal solution in terms of time and space complexity?

easy

A. Count character frequencies using a fixed-size array indexed by character codes, then verify counts match.

B. Use a greedy approach to match characters from one string to the other sequentially.

C. Sort both strings and compare them character by character.

D. Use dynamic programming to check all possible rearrangements.

Solution

1. Step 1: Understand problem constraints

   Since strings contain only lowercase letters, a fixed-size array of length 26 can track character counts efficiently.

2. Step 2: Compare frequency counts

   Increment counts for the first string and decrement for the second; if any count goes negative, strings differ.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Counting frequencies with a fixed array is O(n) time and O(1) space [OK]

Hint: Frequency counting with fixed array is optimal [OK]

Common Mistakes:

• Assuming sorting is always best
• Trying greedy matching
• Using DP unnecessarily

3. The following code attempts to count subarrays summing to k. Which line contains a subtle bug that causes incorrect counts for subarrays starting at index 0?

medium

A. Line 7: if prefix_sum - k in prefix_counts (wrong condition)

B. Line 5: prefix_sum += num (incorrect accumulation)

C. Line 3: prefix_counts = {} (missing initialization with {0:1})

D. Line 9: prefix_counts[prefix_sum] = prefix_counts.get(prefix_sum, 0) + 1 (incorrect update)

Solution

1. Step 1: Identify initialization of prefix_counts

   prefix_counts must start with {0:1} to count subarrays starting at index 0 correctly.

2. Step 2: Check other lines

   Accumulation, condition, and update lines are correct; only initialization is missing the base case.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Missing {0:1} causes missed counts for subarrays from start [OK]

Hint: Always initialize prefix_counts with {0:1} to handle subarrays from index 0 [OK]

Common Mistakes:

• Not initializing prefix_counts with {0:1}
• Misplacing prefix_sum updates
• Incorrect condition checks

4. What is the time complexity of the optimal frequency counting approach for checking if two strings of length n are anagrams, assuming the strings contain only lowercase English letters?

medium

A. O(n log n) due to sorting the strings

B. O(n) because each string is traversed once and frequency updates are O(1)

C. O(n * 26) because for each character you update a frequency array of size 26

D. O(1) since the frequency array size is fixed and independent of input length

Solution

1. Step 1: Identify loops over input strings

   Both strings are traversed once, each iteration doing O(1) work updating counts.

2. Step 2: Analyze frequency array operations

   Frequency array is fixed size 26, so updates are constant time, not multiplied by n.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Overall time is linear in string length n [OK]

Hint: Frequency updates are O(1), total O(n) time [OK]

Common Mistakes:

• Confusing sorting complexity with counting
• Multiplying by 26 unnecessarily
• Assuming constant time overall

5. Suppose the problem changes: now elements from the arrays can be reused multiple times in the intersection (i.e., unlimited reuse). Which modification to the algorithm correctly handles this new requirement?

hard

A. Use a hash map to count frequencies in one array and for each element in the other array, add it to intersection if count > 0 without decrementing counts.

B. Use the same two-pointer approach but do not increment pointers when elements match, allowing reuse.

C. Use a hash map to count frequencies in one array and for each element in the other array, add it to intersection and decrement count accordingly.

D. Sort both arrays and use two pointers, but reset pointers to zero after each match to allow reuse.

Solution

1. Step 1: Understand reuse requirement

   Elements can be reused unlimited times, so counts should not be decremented after matching.

2. Step 2: Evaluate modifications

   Two-pointer approach relies on moving pointers forward, so it cannot handle reuse without complex resets. Hash map counting without decrementing counts allows unlimited reuse correctly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Hash map frequency counting without decrement handles reuse correctly [OK]

Hint: Do not decrement counts to allow reuse [OK]

Common Mistakes:

• Not changing pointer logic for reuse
• Decrementing counts incorrectly
• Resetting pointers causing infinite loops