Problem Description

You need to determine if two strings are isomorphic. Two strings s and t are considered isomorphic when you can replace characters in s to transform it into t.

The replacement must follow these rules:

• Each character in s must map to exactly one character in t
• Each character in t must be mapped to by exactly one character in s (one-to-one mapping)
• A character can map to itself
• The mapping must be consistent - if character 'a' maps to 'b', then every occurrence of 'a' must map to 'b'
• The order of characters must be preserved

For example:

• "egg" and "add" are isomorphic because we can map: e→a, g→d
• "foo" and "bar" are NOT isomorphic because 'o' would need to map to both 'a' and 'r'
• "paper" and "title" are isomorphic with mapping: p→t, a→i, e→l, r→e

The solution uses two dictionaries to track the bidirectional mapping between characters. d1 maps characters from s to t, while d2 maps characters from t to s. As we iterate through both strings simultaneously, we check if any character already has a different mapping than what we're trying to establish. If we find a conflict (a character trying to map to multiple different characters), we return False. If we successfully process all characters without conflicts, the strings are isomorphic.

Intuition

The key insight is recognizing that isomorphic strings require a bijective mapping (one-to-one correspondence) between characters. Think of it like creating a cipher where each letter consistently translates to exactly one other letter.

When we see a character in string s, it must always map to the same character in string t. Similarly, when we see a character in string t, it must always come from the same character in string s. This bidirectional constraint is crucial - it's not enough to just check one direction.

Why do we need two dictionaries? Consider what could go wrong with just one:

• If we only track s→t mappings, we might miss cases where two different characters in s try to map to the same character in t
• If we only track t→s mappings, we might miss cases where one character in s tries to map to multiple characters in t

By maintaining both d1 (mapping from s to t) and d2 (mapping from t to s), we can catch violations in both directions:

• When we see character a in s and b in t, we check: Has a already been mapped to something other than b? Has b already been mapped from something other than a?
• If either check fails, the strings cannot be isomorphic

The solution naturally emerges from this understanding: traverse both strings together, build the mapping relationships, and immediately return False if we detect any inconsistency. If we complete the traversal without conflicts, the bijective mapping exists, confirming the strings are isomorphic.

Solution Approach

We implement the solution using two hash tables (dictionaries in Python) to maintain the bidirectional character mapping between strings s and t.

Data Structures:

• d1: Dictionary mapping characters from s to t
• d2: Dictionary mapping characters from t to s

Algorithm Steps:

1. Initialize two empty dictionaries d1 and d2 to store the character mappings.

2. Iterate through both strings simultaneously using zip(s, t), which pairs up characters at the same positions:

   • For each pair (a, b) where a is from s and b is from t

3. Check for mapping conflicts:

   • If a already exists in d1 but maps to a different character than b: (a in d1 and d1[a] != b)
   • If b already exists in d2 but maps to a different character than a: (b in d2 and d2[b] != a)
   • If either condition is true, return False immediately

4. Update the mappings:

   • Set d1[a] = b to record that character a maps to character b
   • Set d2[b] = a to record that character b is mapped from character a

5. Return the result:

   • If we complete the iteration without finding any conflicts, return True

Time Complexity: O(n) where n is the length of the strings, as we traverse both strings once.

Space Complexity: O(k) where k is the number of unique characters in the strings. In the worst case, this could be O(n) if all characters are unique.

The solution elegantly handles all the requirements: it ensures one-to-one mapping, preserves order (by iterating sequentially), and allows self-mapping (no special case needed).

Example Walkthrough

Let's trace through the algorithm with the example: s = "paper" and t = "title"

Initial state:

• d1 = {} (maps s→t)
• d2 = {} (maps t→s)

Iteration 1: a = 'p', b = 't'

• Check: Is 'p' in d1? No. Is 't' in d2? No.
• No conflicts, update mappings:
• d1 = {'p': 't'}
• d2 = {'t': 'p'}

Iteration 2: a = 'a', b = 'i'

• Check: Is 'a' in d1? No. Is 'i' in d2? No.
• No conflicts, update mappings:
• d1 = {'p': 't', 'a': 'i'}
• d2 = {'t': 'p', 'i': 'a'}

Iteration 3: a = 'p', b = 't'

• Check: Is 'p' in d1? Yes, it maps to 't'. Does it equal 't'? Yes. ✓
• Check: Is 't' in d2? Yes, it maps to 'p'. Does it equal 'p'? Yes. ✓
• No conflicts, mappings remain unchanged (already correct)

Iteration 4: a = 'e', b = 'l'

• Check: Is 'e' in d1? No. Is 'l' in d2? No.
• No conflicts, update mappings:
• d1 = {'p': 't', 'a': 'i', 'e': 'l'}
• d2 = {'t': 'p', 'i': 'a', 'l': 'e'}

Iteration 5: a = 'r', b = 'e'

• Check: Is 'r' in d1? No. Is 'e' in d2? No.
• No conflicts, update mappings:
• d1 = {'p': 't', 'a': 'i', 'e': 'l', 'r': 'e'}
• d2 = {'t': 'p', 'i': 'a', 'l': 'e', 'e': 'r'}

Result: No conflicts found during the entire traversal, return True.

Now let's see a failing case with s = "foo" and t = "bar":

Iteration 1: a = 'f', b = 'b'

• d1 = {'f': 'b'}, d2 = {'b': 'f'}

Iteration 2: a = 'o', b = 'a'

• d1 = {'f': 'b', 'o': 'a'}, d2 = {'b': 'f', 'a': 'o'}

Iteration 3: a = 'o', b = 'r'

• Check: Is 'o' in d1? Yes, it maps to 'a'. Does it equal 'r'? No! ✗
• Conflict detected: 'o' cannot map to both 'a' and 'r'
• Return False immediately

Solution Implementation

Time and Space Complexity

The time complexity is O(n) where n is the length of the input strings s and t. The algorithm iterates through both strings once using the zip function, and for each character pair, it performs constant-time dictionary operations (lookup and insertion).

The space complexity is O(C) where C is the size of the character set. In the worst case, each unique character in the strings gets mapped in the dictionaries d1 and d2. Since the problem deals with ASCII characters, C = 256 represents the maximum possible unique characters that could be stored in each dictionary. Therefore, the space used by both dictionaries is bounded by 2 * C = O(C).

Common Pitfalls

Pitfall 1: Using Only One Dictionary (Unidirectional Mapping)

A frequent mistake is attempting to solve this problem using only a single dictionary to map from s to t, without checking the reverse mapping. This fails to ensure the one-to-one (bijective) relationship required for isomorphism.

Incorrect Approach:

def isIsomorphic(self, s: str, t: str) -> bool:
    mapping = {}
    for char_s, char_t in zip(s, t):
        if char_s in mapping and mapping[char_s] != char_t:
            return False
        mapping[char_s] = char_t
    return True

Why it fails: Consider s = "badc" and t = "baba". Using only one dictionary:

• b → b, a → a, d → b, c → a
• This passes the single dictionary check, but it's incorrect because both b and d map to b, violating the one-to-one mapping rule.

Solution: Always use two dictionaries to track both forward and reverse mappings, ensuring each character in t is mapped to by exactly one character in s.

Pitfall 2: Forgetting to Check Existing Mappings Before Assignment

Another mistake is updating the dictionaries without first checking if a conflicting mapping already exists, leading to overwriting previous mappings.

Incorrect Approach:

def isIsomorphic(self, s: str, t: str) -> bool:
    s_to_t = {}
    t_to_s = {}
    for char_s, char_t in zip(s, t):
        s_to_t[char_s] = char_t  # Assigns without checking
        t_to_s[char_t] = char_s
        if s_to_t[char_s] != char_t or t_to_s[char_t] != char_s:
            return False
    return True

Why it fails: The check happens after assignment, so it will always pass since we just set those exact values. The original mapping gets overwritten before we can detect the conflict.

Solution: Always check for existing mappings before updating the dictionaries. The condition should verify if a key exists AND has a different value than what we're trying to map.

Pitfall 3: Assuming Equal String Lengths

While most implementations assume strings have equal length (and many problem statements guarantee this), it's good practice to handle edge cases.

Defensive Programming:

def isIsomorphic(self, s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    # ... rest of the solution

Solution: Add a length check at the beginning if the problem doesn't guarantee equal-length strings. This prevents potential issues with zip() silently truncating to the shorter string's length.