String Transforms Into Another String

hard hash map string greedy

Problem

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 pick a character that occurs in the current str1 and replace all of its occurrences with any other lowercase letter. All occurrences of the chosen character must be converted at the same time. Return true if and only if str1 can be transformed into str2.

Inputstr1 = "aabcc", str2 = "ccdee"

Outputtrue

Convert 'c' → 'e', then 'b' → 'd', then 'a' → 'c'. Doing the conversions in the right order avoids clobbering a value that is still needed.

str1

str2

def can_convert(str1, str2):
    if str1 == str2:
        return True
    mapping = {}
    for a, b in zip(str1, str2):
        if a in mapping:
            if mapping[a] != b:
                return False
        else:
            mapping[a] = b
    return len(set(str2)) < 26

function canConvert(str1, str2) {
  if (str1 === str2) return true;
  const mapping = new Map();
  for (let i = 0; i < str1.length; i++) {
    const a = str1[i], b = str2[i];
    if (mapping.has(a)) {
      if (mapping.get(a) !== b) return false;
    } else {
      mapping.set(a, b);
    }
  }
  return new Set(str2).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 a = str1.charAt(i), b = str2.charAt(i);
            if (mapping.containsKey(a)) {
                if (mapping.get(a) != b) return false;
            } else {
                mapping.put(a, b);
            }
        }
        return new HashSet<>(
            str2.chars().mapToObj(c -> (char) c).collect(
                java.util.stream.Collectors.toList())).size() < 26;
    }
}

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

Explanation

Each conversion turns all copies of one letter into another, so a given source letter must always become the same target letter. The solution checks this consistency with a hash map, plus one clever spare-letter check.

If str1 already equals str2, we are done — return True with zero conversions.

Otherwise we scan the strings together and build a mapping str1[i] → str2[i]. If a letter is ever asked to map to two different targets, that is impossible (one letter cannot become two things), so we return False.

Even with a consistent mapping, conversions can clash in a cycle (like a→b while b→a). To untangle a cycle you need a temporary spare letter to park a value in. That spare exists only if str2 uses fewer than 26 distinct letters, which is the final len(set(str2)) < 26 check.

Example: "aabcc" → "ccdee". The mapping a→c, b→d, c→e is consistent, and str2 uses only 3 letters (under 26), so a spare is available — answer True.

Time: O(n) Space: O(1)