Watch 9 video solutions for String Transforms Into Another String, a hard level problem involving Hash Table, String. This walkthrough by Kelvin Chandra has 4,532 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |