What pattern does Isomorphic Strings use?

The Pattern: Hash Maps (One-to-One Mapping Validation) The Heuristic: When verifying a one-to-one mapping between two sequences, maintain a forward mapping and a set of used targets to ensure uniqueness and consistency in a single pass.

Isomorphic Strings - LeetCode Solution

Q: What is the time complexity of Isomorphic Strings?

O(n). The algorithm iterates through the strings once, performing O(1) average-time hash map and set operations per character.

Problem

Given two strings s and t, determine if they are isomorphic such that the characters in s can be replaced to get t, with a one-to-one mapping between characters and no two characters mapping to the same character.

1 ≤ s.length ≤ 5 * 10⁴
t.length == s.length
s and t consist of any valid ASCII characters.

Example

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

Output: true

The character 'e' in s maps to 'a' in t, and 'g' maps to 'd'. The mapping is consistent and one-to-one, so the strings are isomorphic. Consider the strings s = "foo" and t = "bar". The first 'f' maps to 'b', but the second 'o' would need to map to both 'a' and 'r', which is impossible. Thus, they are not isomorphic. The critical insight is that each character in s must map to exactly one character in t, and no two characters in s can map to the same character in t.

Approach

Straightforward Solution

A brute-force approach might try all possible mappings between characters of s and t, which is exponential and infeasible for large strings.

Core Observation

Isomorphism requires a bijection between characters of s and t: each character in s maps to exactly one character in t, and no two characters in s map to the same character in t.

Path to Optimal

The key recognition signals are 'one-to-one mapping' and 'character replacement' which indicate the use of Hash Maps to track mappings from s to t and a set to track used characters in t. This allows checking the mapping consistency in a single pass over the strings.

Optimal Approach

Iterate through both strings simultaneously, maintaining a hash map from characters in s to characters in t and a set of characters already mapped in t. For each character pair, if the character in s is not mapped, check if the character in t is already used; if so, return false. Otherwise, add the mapping and mark the character in t as used. If the character in s is mapped, verify it maps to the current character in t. If any inconsistency is found, return false. If the loop completes, return true.

Time

O(n)

The algorithm iterates through the strings once, performing O(1) average-time hash map and set operations per character.

Space

O(n)

In the worst case, the hash map and set store mappings for all characters in s and t, which is proportional to the length of the strings.

Solution

1class Solution:
2    def isIsomorphic(self, s: str, t: str) -> bool:
3
4        mapping = {}
5        used = set()
6
7        for i in range(len(s)):
8
9            c1 = s[i]
10            c2 = t[i]
11
12            if c1 not in mapping:
13                if c2 in used:
14                    return False
15
16                mapping[c1] = c2
17                used.add(c2)
18
19            else:
20                if mapping[c1] != c2:
21                    return False
22
23        return True

Step-by-Step Solution

1

Track Character Mappings and Used Targets to Validate Isomorphism

4mapping = {}
5used = set()

Objective

To maintain a mapping from characters in s to characters in t and track which characters in t have been used to ensure a one-to-one mapping.

Key Insight

By storing the mapping from s to t in a hash map and tracking used characters in t with a set, the algorithm can efficiently verify both the consistency of mappings and the uniqueness constraint in a single pass. This avoids the need for nested loops or backtracking and guarantees O(n) time complexity.

Interview Quick-Check

Core Logic

Maintain a hash map for s->t mappings and a set for used characters in t to enforce one-to-one mapping constraints.

State & Boundaries

Check mapping existence before adding new mappings and verify consistency for existing mappings.

Common Pitfalls & Bugs

Failing to check if a character in t is already used by another character in s can lead to incorrect acceptance of non-isomorphic strings.

2

Iterate Through Characters to Build and Validate Mappings

7for i in range(len(s)):
  c1 = s[i]
  c2 = t[i]
  if c1 not in mapping:
      if c2 in used:
          return False
      mapping[c1] = c2
      used.add(c2)
  else:
      if mapping[c1] != c2:
          return False

Objective

To iterate through each character pair in s and t, updating the mapping and used set or returning false if a conflict is detected.

Key Insight

The iteration simultaneously examines corresponding characters in s and t. If the character in s is unmapped, the algorithm ensures the character in t is unused before creating a new mapping. If the character in s is already mapped, it verifies the mapping matches the current character in t. This step enforces the bijection property incrementally and efficiently.

Interview Quick-Check

Core Logic

For each character pair, either establish a new mapping if possible or verify existing mapping consistency.

State & Boundaries

Return false immediately upon detecting a mapping conflict to avoid unnecessary computation.

Common Pitfalls & Bugs

Not returning false immediately upon conflict can lead to incorrect results or wasted computation.

3

Return True After Successful Validation of All Mappings

23	`return True`

Objective

To confirm that all character mappings are consistent and unique, returning true to indicate isomorphism.

Key Insight

If the iteration completes without returning false, it means every character in s maps uniquely and consistently to a character in t. Returning true signals that the strings are isomorphic under the defined constraints.

Interview Quick-Check

Core Logic

Returning true after full iteration confirms the bijection property holds for all character pairs.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 13 Critical

if c2 in used:

Check if the current character in t is already used by another character in s.

This check enforces the uniqueness constraint of the mapping, preventing two characters in s from mapping to the same character in t.

Line 14 Critical

return False

Return false if the character in t is already used, violating uniqueness.

Immediate termination upon detecting a mapping conflict prevents incorrect acceptance of non-isomorphic strings and saves computation.

Line 20 Critical

if mapping[c1] != c2:

Check if the existing mapping for the current character in s matches the current character in t.

Verifying mapping consistency ensures that the established bijection is not violated by conflicting character pairs.

Line 21 Critical

return False

Return false if the mapping is inconsistent.

Immediate termination upon inconsistency prevents incorrect acceptance of non-isomorphic strings and maintains correctness.

Line 4 Core

mapping = {}

Initialize a hash map to store character mappings from s to t.

This data structure enables O(1) average-time lookups and insertions, which is essential for efficiently tracking the mapping relationships between characters.

Line 5 Core

used = set()

Initialize a set to track characters in t that have already been mapped.

Tracking used characters in t prevents multiple characters in s from mapping to the same character in t, enforcing the uniqueness constraint of the bijection.

Line 16 Core

mapping[c1] = c2

Assign the mapping from the current character in s to the current character in t.

Establishing the mapping is essential to track the correspondence between characters and enforce consistency in future iterations.

Line 17 Core

used.add(c2)

Mark the current character in t as used.

Recording the usage of the character in t prevents future characters in s from mapping to it, preserving the one-to-one mapping property.

Line 23 Core

return True

Return true after successfully validating all character mappings.

Completing the iteration without conflicts confirms the strings are isomorphic under the one-to-one mapping constraints.

Line 12 Core

if c1 not in mapping:

Check if the current character in s has no existing mapping.

Determining whether to create a new mapping or verify an existing one is critical to maintaining mapping consistency.

Line 19 Core

else:

Handle the case where the current character in s already has a mapping and must be validated.

If the character from s already has an established mapping, the algorithm must verify that the current character in t matches that mapping to maintain consistency.

Line 7 Standard

for i in range(len(s)):

Begin iterating over the indices of the strings.

Iterating through the strings simultaneously allows the algorithm to examine corresponding character pairs to build or verify mappings.

Line 9 Standard

c1 = s[i]

Retrieve the current character from s.

Accessing the character in s at the current index is necessary to check or establish its mapping.

Line 10 Standard

c2 = t[i]

Retrieve the current character from t.

Accessing the character in t at the current index is necessary to verify or assign the mapping target.

Test Your Understanding

Why is it necessary to check both that a character in s maps consistently to a character in t and that no two characters in s map to the same character in t?

Because isomorphism requires a bijection: each character in s must map to exactly one character in t (consistency), and no two characters in s can map to the same character in t (uniqueness). Checking only one direction can miss conflicts that violate the one-to-one mapping.

Don't just read it. Drill it.

Reconstruct Isomorphic Strings from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Isomorphic Strings drill

or drill a free problem

7	`for i in range(len(s)):`
9	`c1 = s[i]`
10	`c2 = t[i]`
12	`if c1 not in mapping:`
13	`if c2 in used:`
14	`return False`
16	`mapping[c1] = c2`
17	`used.add(c2)`
19	`else:`
20	`if mapping[c1] != c2:`
21	`return False`

1	`class Solution:`
2	`def isIsomorphic(self, s: str, t: str) -> bool:`
3
4	`mapping = {}`
5	`used = set()`
6
7	`for i in range(len(s)):`
8
9	`c1 = s[i]`
10	`c2 = t[i]`
11
12	`if c1 not in mapping:`
13	`if c2 in used:`
14	`return False`
15
16	`mapping[c1] = c2`
17	`used.add(c2)`
18
19	`else:`
20	`if mapping[c1] != c2:`
21	`return False`
22
23	`return True`

Problem

Example

Approach

Solution

Step-by-Step Solution

Track Character Mappings and Used Targets to Validate Isomorphism

Iterate Through Characters to Build and Validate Mappings

Return True After Successful Validation of All Mappings

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.