LeetCode 1153 - String Transforms Into Another String

The problem gives us two strings, str1 and str2, which are guaranteed to have the same length. We want to determine whether it is possible to transform str1 into str2 using a sequence of character conversion operations.

leetcodehardhash-tablestringgraph-theory

LeetCode Problem 1153

Difficulty: 🔴 Hard
Topics: Hash Table, String, Graph Theory

Solution

Problem Understanding

The problem gives us two strings, str1 and str2, which are guaranteed to have the same length. We want to determine whether it is possible to transform str1 into str2 using a sequence of character conversion operations.

A single conversion operation works as follows:

  • Choose one character in str1
  • Replace every occurrence of that character with another lowercase English letter

The important detail is that the replacement affects all occurrences simultaneously. We cannot selectively replace only some occurrences of a character.

For example, if the current string is "aabcc" and we convert 'a' to 'c', the entire string becomes "ccbcc" because every 'a' changes at once.

The goal is to determine whether there exists some sequence of these operations that transforms the entire string exactly into str2.

The constraints are important:

  • Both strings have length up to 10^4
  • Only lowercase English letters are used
  • There are only 26 possible characters

The small alphabet size is the key observation that allows an efficient solution.

A critical property of the operation is consistency. If one occurrence of 'a' in str1 maps to 'c' in str2, then every occurrence of 'a' must also map to 'c'. Otherwise, the transformation is impossible because conversions always affect all copies of a character simultaneously.

For example:

  • "aa" → "bc" is impossible
  • The first 'a' would need to become 'b'
  • The second 'a' would need to become 'c'
  • A single character cannot map to two different targets

Another subtle edge case involves cycles. Consider:

  • "ab" → "ba"

At first glance, it looks possible because:

  • 'a' maps to 'b'
  • 'b' maps to 'a'

However, this creates a cycle. If we convert 'a' to 'b' first, we lose the ability to distinguish original 'b' characters from converted ones. To break such a cycle, we need a temporary unused character.

Since there are only 26 lowercase letters, if all 26 characters are already used in the target string, there is no spare temporary character available to break cycles.

The problem guarantees:

  • Equal string lengths
  • Only lowercase English letters
  • Non-empty strings

These guarantees simplify the implementation because we do not need to handle invalid input.

Approaches

Brute Force Approach

A brute force strategy would attempt to simulate every possible sequence of conversions.

We could model the problem as a graph search where:

  • Each node represents a current string state
  • Each edge represents one valid conversion operation

Starting from str1, we would try all possible character replacements and search for a path to str2.

This approach is theoretically correct because it explores all possible transformation sequences. If a valid sequence exists, exhaustive search will eventually find it.

However, the number of possible states is enormous. For each step:

  • We may choose up to 26 characters
  • Each may be converted into 26 possible targets
  • Strings can have length up to 10^4

The state space grows exponentially, making this completely infeasible.

The brute force approach fails because the search space is far too large.

Optimal Approach

The key insight is that the actual sequence of operations is less important than the mapping relationship between characters.

Suppose we examine corresponding positions in the strings:

  • If str1[i] = 'a' and str2[i] = 'c'
  • Then every 'a' in str1 must ultimately become 'c'

This creates a deterministic mapping:

  • One source character must map to exactly one target character

If we ever discover:

  • 'a' -> 'b'
  • and later 'a' -> 'c'

then the transformation is impossible immediately.

Once the mapping consistency is verified, the only remaining issue is cycles.

A cycle such as:

  • 'a' -> 'b'
  • 'b' -> 'a'

requires an unused temporary character to break safely.

If str2 already uses all 26 letters, there is no spare character available. In that case:

  • Any non-trivial cycle makes the transformation impossible

Fortunately, we do not even need to explicitly detect cycles.

A remarkable observation is:

  • If str1 != str2
  • and str2 uses all 26 characters
  • then transformation is impossible

Why?

Because any change would eventually require temporary storage to avoid overwriting information, but no unused character exists.

So the final conditions are:

  1. The character mapping must be consistent
  2. Either:
  • str1 == str2, or
  • str2 uses fewer than 26 distinct letters
Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Explores all possible conversion sequences
Optimal O(n) O(1) Uses mapping consistency and cycle observation

Algorithm Walkthrough

  1. First, check whether str1 and str2 are already identical.

If they are equal, no conversions are needed, so we immediately return true. 2. Create a hash map to store character mappings.

The key will be a character from str1, and the value will be the corresponding character in str2.

This ensures each source character maps consistently to exactly one destination character. 3. Iterate through both strings simultaneously.

For every index i:

  • Let source = str1[i]
  • Let target = str2[i]
  1. Check whether source already exists in the mapping.

  • If it does not exist, insert the mapping:

  • source -> target

  • If it already exists, verify the stored target matches the current target.

  1. If the existing mapping conflicts with the current target, return false.

Example:

  • Earlier we saw 'a' -> 'b'
  • Now we see 'a' -> 'c'

This is impossible because one conversion operation cannot produce two different characters. 6. After processing all characters, compute how many distinct characters appear in str2.

We use a set for this because sets automatically remove duplicates. 7. If str2 contains fewer than 26 distinct characters, return true.

This means there is at least one unused character available as temporary storage for resolving cycles. 8. Otherwise, return false.

If all 26 characters are used and the strings are not already equal, cycles cannot be resolved safely.

Why it works

The algorithm works because every valid transformation induces a consistent character mapping. Since conversions affect all occurrences simultaneously, a single source character cannot map to multiple targets.

Once mapping consistency is guaranteed, the only remaining obstacle is cyclic dependencies. Cycles can always be resolved if there exists at least one unused temporary character. Therefore, having fewer than 26 distinct target characters guarantees that transformations are possible whenever the mapping is consistent.

Python Solution

class Solution:
    def canConvert(self, str1: str, str2: str) -> bool:
        if str1 == str2:
            return True

        char_map = {}

        for source_char, target_char in zip(str1, str2):
            if source_char in char_map:
                if char_map[source_char] != target_char:
                    return False
            else:
                char_map[source_char] = target_char

        return len(set(str2)) < 26

The implementation begins with an early equality check. If both strings are already identical, no operations are required, so the answer is immediately True.

Next, we create char_map, which stores the required transformation for each source character.

The loop processes both strings position by position using zip. For every character pair:

  • If the source character already has a mapping, we verify consistency.
  • If the mapping conflicts, we return False.
  • Otherwise, we record the mapping.

After validating the mapping rules, the code checks how many distinct characters appear in str2.

If fewer than 26 unique characters are used, at least one spare character exists, allowing cyclic transformations to be resolved safely.

If all 26 letters are used, the transformation is impossible unless the strings were already identical, which we handled earlier.

Go Solution

func canConvert(str1 string, str2 string) bool {
    if str1 == str2 {
        return true
    }

    charMap := make(map[byte]byte)

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

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

    distinctChars := make(map[byte]bool)

    for i := 0; i < len(str2); i++ {
        distinctChars[str2[i]] = true
    }

    return len(distinctChars) < 26
}

The Go implementation follows the same logic as the Python version.

The main difference is that Go strings are indexed as byte arrays because the input contains only lowercase English letters. This avoids any Unicode complications.

Mappings are stored using map[byte]byte, and the distinct character count is implemented using map[byte]bool.

Go does not have a built-in set type, so the boolean map serves as a set replacement.

Worked Examples

Example 1

Input:
str1 = "aabcc"
str2 = "ccdee"

We process each position one by one.

Index str1[i] str2[i] Mapping State
0 a c {a: c}
1 a c {a: c}
2 b d {a: c, b: d}
3 c e {a: c, b: d, c: e}
4 c e {a: c, b: d, c: e}

No conflicts occur.

Distinct characters in str2:

  • {c, d, e}
  • Count = 3

Since 3 < 26, a temporary character exists.

Result:

true

Possible transformation sequence:

aabcc
aabee   (c -> e)
aadee   (b -> d)
ccdee   (a -> c)

Example 2

Input:
str1 = "leetcode"
str2 = "codeleet"

Process the mappings:

Index str1[i] str2[i] Mapping State
0 l c {l: c}
1 e o {l: c, e: o}
2 e d Conflict

At index 2:

  • 'e' was already mapped to 'o'
  • Now it must map to 'd'

This violates consistency.

Result:

false

Complexity Analysis

Measure Complexity Explanation
Time O(n) We scan both strings once
Space O(1) At most 26 character mappings and 26 set entries

The algorithm processes each character exactly once, giving linear time complexity relative to the string length.

Although we use hash maps and sets, the alphabet size is fixed at 26 lowercase letters. Therefore, the extra memory usage never grows beyond a constant bound.

Test Cases

solution = Solution()

assert solution.canConvert("aabcc", "ccdee") == True
# Basic valid transformation

assert solution.canConvert("leetcode", "codeleet") == False
# Inconsistent mapping

assert solution.canConvert("abc", "abc") == True
# Already equal strings

assert solution.canConvert("aa", "bc") == False
# Same source character maps to different targets

assert solution.canConvert("ab", "ba") == True
# Simple cycle, possible because spare character exists

assert solution.canConvert(
    "abcdefghijklmnopqrstuvwxyz",
    "bcdefghijklmnopqrstuvwxyza"
) == False
# Full 26-character cycle with no spare character

assert solution.canConvert("a", "b") == True
# Single character conversion

assert solution.canConvert("abcdefghijklmnopqrstuvwxyz",
                           "abcdefghijklmnopqrstuvwxyz") == True
# All 26 characters used, but strings already equal

assert solution.canConvert("abca", "zbxz") == True
# Multiple consistent mappings

assert solution.canConvert("abab", "cdcd") == True
# Repeated pattern mapping

assert solution.canConvert("abab", "cdce") == False
# Conflicting mapping for repeated character
Test Why
"aabcc" → "ccdee" Standard valid transformation
"leetcode" → "codeleet" Detects inconsistent mapping
"abc" → "abc" No operations needed
"aa" → "bc" Same source maps to different targets
"ab" → "ba" Valid cycle with spare character
Full alphabet rotation Impossible cycle with no spare letter
"a" → "b" Smallest non-trivial input
Full alphabet identical Edge case where all letters used but already equal
"abca" → "zbxz" Consistent repeated mappings
"abab" → "cdcd" Pattern-preserving transformation
"abab" → "cdce" Repeated character conflict

Edge Cases

Strings Are Already Equal

If str1 and str2 are identical, the answer is always true because zero operations are allowed.

This edge case is important because even when all 26 letters are used, no transformation is necessary. A naive implementation that only checks the distinct character count might incorrectly return false.

The implementation handles this with an immediate early return:

if str1 == str2:
    return True

One Character Maps to Multiple Targets

Consider:

str1 = "aa"
str2 = "bc"

The first 'a' would need to become 'b', while the second 'a' would need to become 'c'.

This is impossible because conversions affect all occurrences simultaneously.

The implementation detects this by storing mappings in a hash map and verifying consistency every time the same source character appears again.

Full Alphabet Cycle

Consider:

str1 = "abcdefghijklmnopqrstuvwxyz"
str2 = "bcdefghijklmnopqrstuvwxyza"

This forms a complete 26-character cycle.

To perform the transformation safely, we would need a temporary unused character, but all 26 lowercase letters are already present in str2.

Without spare storage, information would be overwritten during conversion.

The implementation correctly handles this by checking:

len(set(str2)) < 26

If all 26 characters are used and the strings are not already identical, the answer must be false.