LeetCode 205 - Isomorphic Strings

The problem asks us to determine whether two strings, s and t, are isomorphic. Two strings are considered isomorphic if there exists a one-to-one mapping between characters in s and characters in t such that replacing every character in s according to this mapping produces t.

leetcodeeasyhash-tablestring

LeetCode Problem 205

Difficulty: 🟢 Easy
Topics: Hash Table, String

Solution

Problem Understanding

The problem asks us to determine whether two strings, s and t, are isomorphic. Two strings are considered isomorphic if there exists a one-to-one mapping between characters in s and characters in t such that replacing every character in s according to this mapping produces t.

In simpler terms, each character in s must consistently map to exactly one character in t, and no two different characters in s can map to the same character in t. However, a character is allowed to map to itself.

For example, in s = "egg" and t = "add":

  • 'e' maps to 'a'
  • 'g' maps to 'd'

This mapping is consistent throughout the string, so the result is true.

By contrast, in s = "f11" and t = "b23":

  • 'f' maps to 'b'
  • '1' first maps to '2'
  • '1' later tries to map to '3'

Since the same character cannot map to multiple characters, the strings are not isomorphic.

The input consists of two strings of equal length. The output is a boolean value:

  • true if a valid one-to-one character mapping exists
  • false otherwise

The constraints tell us several important things:

  • The maximum length is 5 * 10^4, which means an inefficient quadratic solution may become too slow.
  • The strings contain any valid ASCII character, meaning we cannot assume only lowercase letters.
  • The problem guarantees s.length == t.length, so we never need to handle mismatched lengths.

Several edge cases are important to consider upfront. Repeated characters must always map consistently, distinct characters cannot map to the same target character, and single-character strings should always return true. Since ASCII characters are allowed, the solution must also work for digits, punctuation, and mixed character sets.

Approaches

Brute Force Approach

A brute-force solution would try to simulate character replacements while repeatedly checking consistency. For every character pair (s[i], t[i]), we could scan previous positions to verify that the same character in s always matched the same character in t, and that no two different characters mapped to the same target.

For example, when processing index i, we would look through all earlier indices j < i:

  • If s[j] == s[i], then t[j] must equal t[i]
  • If t[j] == t[i], then s[j] must equal s[i]

This guarantees correctness because every mapping rule is explicitly validated. However, for each character we may scan all previous characters, leading to quadratic time complexity.

Given the maximum input size of 50,000, an O(n²) approach would be too slow.

Optimal Approach

The key observation is that we only need to maintain a consistent bidirectional mapping between characters.

A single hash map from s to t is not enough. Consider:

s = "ab"
t = "cc"

A one-way map would allow:

a → c
b → c

But this violates the rule that different characters cannot map to the same character.

To enforce a valid one-to-one correspondence, we maintain two hash maps:

  1. A map from characters in s to characters in t
  2. A map from characters in t to characters in s

As we iterate through the strings:

  • If a character has been seen before, its mapping must match.
  • If it has not been seen, we establish a new mapping in both directions.

This gives us an efficient linear-time solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Compare each character with all previous positions
Optimal O(n) O(n) Use two hash maps to maintain bidirectional mapping

Algorithm Walkthrough

  1. Create two hash maps:
  • s_to_t to map characters from s to t
  • t_to_s to map characters from t to s

We use hash maps because they allow constant-time lookups and updates, making them ideal for validating mappings efficiently. 2. Iterate through both strings simultaneously using their indices. 3. At each position i, retrieve:

  • source_char = s[i]
  • target_char = t[i]
  1. Check whether source_char already exists in s_to_t.

If it exists, verify that it maps to target_char. If not, return False immediately because the mapping is inconsistent. 5. Check whether target_char already exists in t_to_s.

If it exists, verify that it maps back to source_char. If not, return False because two characters are attempting to map to the same target. 6. If neither mapping exists, establish the relationship in both directions:

source_char → target_char
target_char → source_char
  1. Continue until all characters have been processed.
  2. If no conflicts occur, return True.

Why it works

The algorithm maintains the invariant that every processed character pair satisfies a valid one-to-one mapping in both directions. The forward map guarantees consistency for characters in s, while the reverse map guarantees uniqueness in t. Since every position is validated exactly once, any invalid mapping is detected immediately, and a valid mapping across the entire string guarantees the strings are isomorphic.

Python Solution

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        s_to_t: dict[str, str] = {}
        t_to_s: dict[str, str] = {}

        for source_char, target_char in zip(s, t):
            if source_char in s_to_t:
                if s_to_t[source_char] != target_char:
                    return False
            else:
                s_to_t[source_char] = target_char

            if target_char in t_to_s:
                if t_to_s[target_char] != source_char:
                    return False
            else:
                t_to_s[target_char] = source_char

        return True

The implementation starts by creating two dictionaries to maintain the bidirectional mapping between characters.

The loop iterates through both strings simultaneously using zip(s, t), which is a clean and efficient way to process corresponding characters together.

For each character pair, the code first checks whether the current character from s already has a mapping. If it does, the mapping must match the current character in t. Otherwise, the strings cannot be isomorphic.

The same validation is performed in reverse using t_to_s. This prevents multiple characters in s from mapping to the same character in t.

If no conflicts are found after processing all characters, the function returns True.

Go Solution

func isIsomorphic(s string, t string) bool {
	sToT := make(map[byte]byte)
	tToS := make(map[byte]byte)

	for i := 0; i < len(s); i++ {
		sourceChar := s[i]
		targetChar := t[i]

		if mappedChar, exists := sToT[sourceChar]; exists {
			if mappedChar != targetChar {
				return false
			}
		} else {
			sToT[sourceChar] = targetChar
		}

		if mappedChar, exists := tToS[targetChar]; exists {
			if mappedChar != sourceChar {
				return false
			}
		} else {
			tToS[targetChar] = sourceChar
		}
	}

	return true
}

The Go implementation closely mirrors the Python solution. Since the problem guarantees valid ASCII characters, we can safely use byte instead of rune, which simplifies indexing and improves efficiency.

Maps in Go behave similarly to Python dictionaries. The value, exists := map[key] syntax allows us to check whether a mapping already exists and validate consistency.

No special handling for empty strings is needed because the constraints guarantee a minimum length of 1, although the logic would still work correctly for empty inputs.

Worked Examples

Example 1

Input:

s = "egg"
t = "add"
Index s[i] t[i] s_to_t t_to_s Result
0 e a {e: a} {a: e} Valid
1 g d {e: a, g: d} {a: e, d: g} Valid
2 g d unchanged unchanged Valid

Final result: True

The character 'g' consistently maps to 'd', so the strings are isomorphic.

Example 2

Input:

s = "f11"
t = "b23"
Index s[i] t[i] s_to_t t_to_s Result
0 f b {f: b} {b: f} Valid
1 1 2 {f: b, 1: 2} {b: f, 2: 1} Valid
2 1 3 Conflict Conflict Invalid

At index 2, '1' was previously mapped to '2', but now attempts to map to '3'. The algorithm returns False.

Example 3

Input:

s = "paper"
t = "title"
Index s[i] t[i] s_to_t t_to_s Result
0 p t {p: t} {t: p} Valid
1 a i {p: t, a: i} {t: p, i: a} Valid
2 p t unchanged unchanged Valid
3 e l {p: t, a: i, e: l} {t: p, i: a, l: e} Valid
4 r e {p: t, a: i, e: l, r: e} {t: p, i: a, l: e, e: r} Valid

Final result: True

Every repeated character maps consistently, and no two characters share the same target mapping.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character is processed once, with constant-time hash map operations
Space O(n) In the worst case, every character is unique and stored in the maps

The time complexity is linear because the algorithm performs a single pass through the strings. Each lookup and insertion in the hash maps takes average O(1) time.

The space complexity is linear in the number of distinct characters encountered. In the worst case, every character is unique, so both maps together store up to O(n) mappings.

Test Cases

solution = Solution()

assert solution.isIsomorphic("egg", "add") is True      # basic valid mapping
assert solution.isIsomorphic("f11", "b23") is False    # repeated char maps inconsistently
assert solution.isIsomorphic("paper", "title") is True # classic valid case

assert solution.isIsomorphic("ab", "aa") is False      # two chars map to same target
assert solution.isIsomorphic("foo", "bar") is False    # repeated char mismatch
assert solution.isIsomorphic("badc", "baba") is False  # reverse mapping conflict

assert solution.isIsomorphic("a", "b") is True         # single character
assert solution.isIsomorphic("z", "z") is True         # self mapping

assert solution.isIsomorphic("abc", "def") is True     # unique one-to-one mapping
assert solution.isIsomorphic("bbbaaaba", "aaabbbba") is False # complex mismatch

assert solution.isIsomorphic("!@#", "$%^") is True     # special ASCII characters
assert solution.isIsomorphic("11", "22") is True       # repeated digit mapping
assert solution.isIsomorphic("12", "11") is False      # invalid shared mapping
Test Why
"egg", "add" Verifies a standard valid mapping
"f11", "b23" Verifies repeated character inconsistency
"paper", "title" Tests repeated mappings across multiple positions
"ab", "aa" Ensures two characters cannot map to one target
"foo", "bar" Detects inconsistent repeated mapping
"badc", "baba" Validates reverse mapping enforcement
"a", "b" Tests minimum input size
"z", "z" Confirms self-mapping is allowed
"abc", "def" Verifies unique one-to-one mappings
"bbbaaaba", "aaabbbba" Stresses repeated-character logic
"!@#", "$%^" Ensures ASCII special characters work
"11", "22" Tests repeated numeric mapping
"12", "11" Verifies collision detection

Edge Cases

One important edge case is when multiple characters in s try to map to the same character in t. For example, "ab" and "cc" may appear valid if we only check forward consistency. A naive one-way mapping would incorrectly accept this case. The reverse map in our implementation prevents this by ensuring each character in t maps back to exactly one character in s.

Another important case involves repeated characters that must map consistently. For example, "foo" and "bar" fail because 'o' first maps to 'a' and later would need to map to 'r'. The implementation catches this immediately through the forward hash map consistency check.

A third important edge case is strings containing non-letter ASCII characters such as digits or punctuation. Since the problem allows any ASCII character, solutions that assume lowercase letters only may fail. Our implementation treats every character generically through hash maps, so values like "1!1" and "2@2" work correctly without special handling.