Skip to main content
Talentd

String Transforms Into Another String - Solution & Explanation

HardPremiumFree on FleetCodeHash TableString8 min readAsked at: Google
Practice this problem

Problem Statement

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 <= 104
  • str1 and str2 contain only lowercase English letters.

Approach Overview

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.

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Graph Mapping + Cycle DetectionO(n)O(1)Useful when modeling transformations as graph edges and explicitly reasoning about cycles
Hash Table Mapping with Free Character CheckO(n)O(1)Best general solution for interviews and production due to single-pass mapping and simple logic

Video Solution

1153 String Transforms Into Another String (Biweekly Contest 6) • Kelvin Chandra • 4,534 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is String Transforms Into Another String easy or hard?
LeetCode classifies this problem as Hard because of the cycle-breaking edge case. The mapping itself is straightforward, but recognizing that a spare character is required to resolve cycles makes the reasoning more subtle than typical hash map problems.
String Transforms Into Another String Python/Java solution
Most implementations use a hash map or dictionary to store the character mapping and a set to track distinct characters in str2. The algorithm iterates once through both strings, validates the mapping, and then checks whether fewer than 26 unique target characters exist to break cycles.
How to solve String Transforms Into Another String in O(n)?
Scan both strings simultaneously and store a mapping from each character in str1 to the corresponding character in str2 using a hash table. If a character maps to two different targets, return false. After building the mapping, check the number of unique characters in str2. If all 26 characters appear and the strings differ, no temporary character exists to break cycles, making the transformation impossible.
What is the best approach for String Transforms Into Another String?
The hash table mapping approach with a free-character check is the most efficient. Iterate through both strings and enforce a consistent mapping from characters in str1 to str2 using a hash map. After building the mapping, verify that str2 uses fewer than 26 unique characters unless the strings are already identical. This ensures cycles can be broken with a temporary character.
Is String Transforms Into Another String asked at Google/Amazon/Meta?
String transformation and character mapping problems appear frequently in interviews at companies like Google, Amazon, and Meta. They test understanding of hash maps, deterministic mappings, and edge cases involving cycles and limited character sets.
What data structure is used in String Transforms Into Another String?
The main data structure is a hash table (hash map) that stores the mapping from characters in str1 to characters in str2. A set is also used to count distinct characters in the target string. These structures allow constant-time lookups and keep the algorithm linear.
What is the time complexity of String Transforms Into Another String?
The optimal solution runs in O(n) time where n is the length of the strings. You perform a single pass to validate character mappings and track distinct characters in the target string. Space complexity is O(1) because the alphabet size is fixed at 26 lowercase letters.

Ready to solve this problem?

Practice String Transforms Into Another String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters