String Transforms Into Another String

Updated on 25 June, 2025
String Transforms Into Another String header image

Problem Statement

Given two strings, str1 and str2, both of identical length, determine whether it is possible to transform str1 into str2 through a series of character conversions. Each conversion allows changing all occurrences of one specific character in str1 to any other lowercase English letter.

Return true if it is possible to make str1 equal to str2 through such transformations, otherwise return false.


Examples

Example 1

Input:

str1 = "aabcc"
str2 = "ccdee"

Output:

true

Explanation:

Convert 'c' → 'e', then 'b' → 'd', then 'a' → 'c'. The order of conversions matters.

Example 2

Input:

str1 = "vultrcore"
str2 = "corevultr"

Output:

false

Explanation:

There is no way to transform str1 to str2 without causing conflicting character mappings.

Constraints

  • 1 <= str1.length == str2.length <= 10^4
  • str1 and str2 consist of lowercase English letters only.

Approach and Intuition

To determine if the transformation is possible:

  1. Consistent Mapping:

    • Each character in str1 must always map to the same character in str2.
    • If a character maps to multiple targets, return false.
  2. One-to-One Validity:

    • Ensure that two different characters from str1 don't map to the same target in str2, unless that’s unavoidable and a cycle can be broken.
  3. Cycle Handling:

    • If all 26 lowercase characters are already in use in str2, a cycle in the mapping cannot be resolved (since there is no temporary character left to assist), and the transformation is impossible.
  4. Quick Return:

    • If str1 == str2, return true immediately, as no conversion is needed.

This strategy ensures correctness while adhering to the transformation rules, even in edge cases involving cycles or tight letter constraints.

Solutions

  • C++
  • Java
  • Python
cpp
class Solution {
public:
    bool isTransformable(string s1, string s2) {
        if (s1 == s2) {
            return true;
        }
    
        unordered_map<char, char> mapChar;
        unordered_set<char> s2Chars;
    
        for (int i = 0; i < s1.length(); i++) {
            if (mapChar.find(s1[i]) == mapChar.end()) {
                mapChar[s1[i]] = s2[i];
                s2Chars.insert(s2[i]);
            } else if (mapChar[s1[i]] != s2[i]) {
                return false;
            }
        }
    
        if (s2Chars.size() < 26) {
            return true;
        }
    
        return false;
    }
};

This solution checks if one string s1 can be transformed into another string s2 by mapping each character of s1 to characters in s2. The C++ code defines a method isTransformable which returns a boolean indicating whether the transformation is possible. Here's a breakdown of the code:

  • Initialize a mapChar to track mappings from characters in s1 to s2, and a s2Chars set to collect the unique characters in s2.
  • If s1 is identical to s2, return true immediately.
  • Iterate over characters of s1:
    • If the character from s1 has not been mapped, map it to the corresponding character in s2 and add the character from s2 to the set.
    • If the character mapping is inconsistent (a character maps to multiple characters), return false.
  • After the loop, if the size of the s2Chars set is less than 26 (total number of English alphabet letters), return true. This implies there is at least one character in s2 that is not being used and can potentially be used for transformation if needed.
  • If every character in the alphabet is used in s2, return false as the transformation might not be possible due to inability to use characters in s1 that need new mappings to unused characters in s2.

This logic ensures that transformation is possible if characters in s1 either map to themselves in s2 or have consistent mappings without exhausting all possible characters (allowing for necessary transformations).

java
class Solution {
    public boolean isConvertible(String original, String target) {
        if (original.equals(target)) {
            return true;
        }
    
        HashMap<Character, Character> map = new HashMap<>();
        HashSet<Character> usedCharacters = new HashSet<>();
    
        for (int index = 0; index < original.length(); index++) {
            char origChar = original.charAt(index);
            char targetChar = target.charAt(index);
    
            if (!map.containsKey(origChar)) {
                map.put(origChar, targetChar);
                usedCharacters.add(targetChar);
            } else if (map.get(origChar) != targetChar) {
                return false;
            }
        }
    
        return usedCharacters.size() < 26;
    }
}

This Java solution explores the transformation possibility of one string into another by mapping each character from the original string to a corresponding character in the target string. Follow this solution summary to understand how each character mapping and condition contributes to assessing the transformativeness:

  • Start by checking if the original string equals the target string, in which case, return true because no transformation is needed.
  • Initialize a HashMap (map) to associate characters from the original string to the target string, and a HashSet (usedCharacters) to keep track of all characters already used in the transformation.
  • Loop through each character of the original string:
    • If the current original character is not yet mapped, add it to the map with its corresponding character from the target string. Also, add this target character to the set of used characters.
    • If the current original character is already mapped, check if it maps to the same target character. If not, return false, indicating that a transformation is not possible due to conflicting mappings.
  • Check the size of the usedCharacters set. If there are 25 or fewer characters, transformation is possible because there is room to maneuver a character if needed. Return true if possible, otherwise false.

The solution's efficiency lies in its ability to quickly determine transformation feasibility using character mapping and set operations, ensuring that each character has a unique transformation unless they are being reused effectively.

python
class Transformation:
    def canTransform(self, s1: str, s2: str) -> bool:
        if s1 == s2:
            return True
            
        mapping_dict = {}
        unique_chars_in_s2 = set()
            
        for ch1, ch2 in zip(s1, s2):
            if ch1 not in mapping_dict:
                mapping_dict[ch1] = ch2
                unique_chars_in_s2.add(ch2)
            elif mapping_dict[ch1] != ch2:
                return False
            
        return len(unique_chars_in_s2) < 26

In this solution, the given Python function canTransform checks if it is possible to transform one string, s1, into another string, s2, using a character-by-character mapping without any two characters in s1 being mapped to the same character in s2 unless they are identical.

Key details in the solution:

  • Handle the immediate case where the two strings are identical. in such a scenario, return True since no transformation is needed.
  • Utilize a dictionary mapping_dict to maintain the mappings from s1 to s2.
  • Use a set unique_chars_in_s2 to track all unique characters that have been mapped to from s1.
  • Iterate over pairs of characters from s1 and s2 simultaneously:
    • if a character from s1 has not been mapped yet, map it and add the corresponding character from s2 to the set of unique characters.
    • If there's already a mapping for a character, check if it conflicts with the new character from s2; if it does, the transformation is not possible, hence return False.
  • Finally, ensure the total number of unique mapped characters in s2 is less than 26. This is essential since the transformation can only occur if there is, at least, one character in the alphabet that has not been used in s2, allowing for reversible transformations if necessary.

The function returns:

  • True if the transformation is possible under the provided conditions.
  • False otherwise.

Comments

No comments yet.