Given two strings str1 and str2 of the same length, determine whether you can transform str1 into str2 by doing zero or more conversions.
In one conversion you can convert all occurrences of one character in str1 to any other lowercase English character.
Return true if and only if you can transform str1 into str2.
Example 1:
Input: str1 = "aabcc", str2 = "ccdee" Output: true Explanation: Convert 'c' to 'e' then 'b' to 'd' then 'a' to 'c'. Note that the order of conversions matter.
Example 2:
Input: str1 = "leetcode", str2 = "codeleet" Output: false Explanation: There is no way to transform str1 to str2.
Constraints:
1 <= str1.length == str2.length <= 104str1 and str2 contain only lowercase English letters.Problem Overview: You are given two strings str1 and str2 of equal length. In one operation you can convert all occurrences of one character in str1 to another lowercase character. The goal is to determine whether a sequence of such operations can transform str1 into str2.
Approach 1: Graph Mapping + Cycle Detection (O(n) time, O(1) space)
Each character transformation can be viewed as a directed edge from a source character to a target character. Build a mapping graph while iterating through both strings. If a character in str1 maps to two different characters in str2, the transformation is impossible. After building the mapping, cycles become the tricky part. For example a → b and b → a creates a cycle that requires a temporary placeholder character to break. If all 26 lowercase characters already appear in str2, no spare character exists to act as a buffer, so such cycles cannot be resolved. This approach models the transformation using ideas similar to problems in hash table and graph processing.
Approach 2: Hash Table Mapping with Free Character Check (O(n) time, O(1) space)
The practical solution uses a hash table to store a mapping from characters in str1 to characters in str2. Iterate through the strings once and enforce a consistent mapping: if str1[i] was previously mapped, the stored value must match str2[i]. This guarantees deterministic transformations. Next check the set of characters used in str2. If str1 already equals str2, the transformation is trivially valid. Otherwise, ensure that str2 uses fewer than 26 distinct characters. Having at least one unused character provides a temporary placeholder to break mapping cycles like a → b → c → a. The algorithm only performs a single pass with constant-size structures because the alphabet is fixed. Problems involving character conversions and mapping constraints often rely on similar string and hashing techniques.
Recommended for interviews: The hash table mapping approach is what interviewers typically expect. It shows you understand deterministic mappings, cycle breaking, and how to use a constant-size alphabet constraint to simplify the problem. Mentioning the cycle issue and the need for a spare character demonstrates deeper reasoning beyond simply building a map.
First, we can check if str1 and str2 are equal. If they are, return true directly.
Then we count the occurrence of each letter in str2. If the occurrence equals 26, it means str2 contains all lowercase letters. In this case, no matter how str1 is transformed, it cannot become str2, so return false directly.
Otherwise, we use an array or hash table d to record the letter each letter in str1 is transformed to. We traverse the strings str1 and str2. If a letter in str1 has been transformed, the transformed letter must be the same as the corresponding letter in str2, otherwise return false.
After the traversal, return true.
The time complexity is O(n), and the space complexity is O(C). Here, n is the length of the string str1, and C is the size of the character set. In this problem, C = 26.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Graph Mapping + Cycle Detection | O(n) | O(1) | Useful when modeling transformations as graph edges and explicitly reasoning about cycles |
| Hash Table Mapping with Free Character Check | O(n) | O(1) | Best general solution for interviews and production due to single-pass mapping and simple logic |
1153 String Transforms Into Another String (Biweekly Contest 6) • Kelvin Chandra • 4,532 views views
Watch 8 more video solutions →Practice String Transforms Into Another String with our built-in code editor and test cases.
Practice on FleetCode