Problem Description

Given two strings str1 and str2 of the same length, the task is to determine if str1 can be transformed into str2 using the following operation as many times as needed:

• Choose any character in str1 and change all its occurrences to any other lowercase English character.

Constraints:

• Each operation changes all occurrences of a chosen character at once.
• You may use the operation any number of times.
• You cannot map two different characters in str1 to the same character in str2 in a single operation.
• Both str1 and str2 consist only of lowercase English letters and are of equal length.

The goal is to return True if it's possible to transform str1 into str2 using the allowed operations, or False otherwise.

Thought Process

At first glance, it seems like you can always convert str1 to str2 by repeatedly replacing characters. However, the key constraints are:

• Each operation replaces all instances of a character at once.
• You cannot map two different characters in str1 to the same character in str2 unless you use an intermediate character.

The brute-force way would be to try all possible transformation sequences, but that's inefficient. Instead, we can analyze the mapping from characters in str1 to str2:

• If any character in str1 would need to be mapped to more than one character in str2, transformation is impossible.
• If the mapping is a permutation (one-to-one and onto), but all 26 lowercase letters are used, there is no "spare" character to use as a temporary placeholder, making some transformations impossible due to cycles.

This leads us to a more optimized solution using character mapping and checking for cycles.

Solution Approach

We solve the problem step-by-step as follows:

1. Check for direct equality:
   • If str1 is already equal to str2, return True.
2. Build the mapping:
   • For each position i, map str1[i] to str2[i].
   • If a character in str1 maps to different characters in str2 at different positions, return False.
3. Check for cycles:
   • If the set of target characters (characters in str2) uses all 26 lowercase letters, and the mapping is a permutation, then there is no "spare" character to use as a temporary placeholder, so transformation is impossible. Return False in this case.
   • Otherwise, transformation is possible. Return True.

We use a hash map (dictionary) for efficient lookups and to ensure each character in str1 maps to only one character in str2.

Example Walkthrough

Let's use the example: str1 = "ab", str2 = "ba"

1. Mapping:
   • 'a' in str1 maps to 'b' in str2.
   • 'b' in str1 maps to 'a' in str2.
2. Check for cycles:
   • Both 'a' and 'b' are used, but not all 26 letters are used. So, we can use an unused character (like 'c') as a temporary placeholder.
3. Transformation steps:
   • Change all 'a' to 'c': "cb"
   • Change all 'b' to 'a': "ca"
   • Change all 'c' to 'b': "ba"
4. Result:
   • Successfully transformed "ab" to "ba" using allowed operations.

Time and Space Complexity

Brute-force approach:

• Would try all possible sequences of operations, leading to exponential time complexity: O(26ⁿ) for string length n.

• Building the mapping and checking for cycles is O(n), where n is the length of the strings.
• Space complexity is O(1) since the mapping and sets are bounded by the number of lowercase letters (26).

Summary

The key insight is to model the transformation as a mapping of characters and to detect if a cycle prevents transformation due to lack of a spare character. By using a hash map to record mappings and a set to check for full alphabet usage, we can efficiently determine if the transformation is possible. This approach is both elegant and optimal, leveraging simple data structures and clear logic to solve the problem.

Code Implementation

class Solution:
    def canConvert(self, str1: str, str2: str) -> bool:
        if str1 == str2:
            return True
        mapping = {}
        for c1, c2 in zip(str1, str2):
            if c1 in mapping:
                if mapping[c1] != c2:
                    return False
            else:
                mapping[c1] = c2
        # If all 26 characters are used as targets, no spare character for swap
        return len(set(str2)) < 26
      

class Solution {
public:
    bool canConvert(string str1, string str2) {
        if (str1 == str2) return true;
        unordered_map<char, char> mapping;
        for (int i = 0; i < str1.size(); ++i) {
            if (mapping.count(str1[i])) {
                if (mapping[str1[i]] != str2[i]) return false;
            } else {
                mapping[str1[i]] = str2[i];
            }
        }
        unordered_set<char> targets(str2.begin(), str2.end());
        return targets.size() < 26;
    }
};
      

class Solution {
    public boolean canConvert(String str1, String str2) {
        if (str1.equals(str2)) return true;
        Map<Character, Character> mapping = new HashMap<>();
        for (int i = 0; i < str1.length(); i++) {
            char c1 = str1.charAt(i), c2 = str2.charAt(i);
            if (mapping.containsKey(c1)) {
                if (mapping.get(c1) != c2) return false;
            } else {
                mapping.put(c1, c2);
            }
        }
        Set<Character> targets = new HashSet<>();
        for (char c : str2.toCharArray()) targets.add(c);
        return targets.size() < 26;
    }
}
      

var canConvert = function(str1, str2) {
    if (str1 === str2) return true;
    let mapping = {};
    for (let i = 0; i < str1.length; i++) {
        let c1 = str1[i], c2 = str2[i];
        if (c1 in mapping) {
            if (mapping[c1] !== c2) return false;
        } else {
            mapping[c1] = c2;
        }
    }
    let targets = new Set(str2);
    return targets.size < 26;
};