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 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.

Examples

Example 1:

1
2
3

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:

1
2
3

Input: str1 = "leetcode", str2 = "codeleet"
Output: false
Explanation: There is no way to transform str1 to str2.

Constraints:

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

Solution

Method 1 - Mapping and Cycle Detection

Intuition

To transform str1 to str2, we need to map each character in str1 to the corresponding character in str2. If a character in str1 maps to more than one character in str2, it’s impossible. If the mapping forms a cycle and all 26 letters are used, we cannot break the cycle (since we have no spare character to use as a temporary placeholder).

Approach

  1. Build a mapping from each character in str1 to the corresponding character in str2.
  2. If a character maps to more than one character, return false.
  3. If str1 == str2, return true.
  4. If the number of unique characters in str2 is less than 26, we can always break cycles using an unused character.
  5. If all 26 characters are used in str2 and there is a cycle, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#include <string>
#include <unordered_map>
#include <unordered_set>
using namespace std;
bool canConvert(string str1, string str2) {
    if (str1 == str2) return true;
    unordered_map<char, char> mp;
    for (int i = 0; i < str1.size(); ++i) {
        if (mp.count(str1[i]) && mp[str1[i]] != str2[i]) return false;
        mp[str1[i]] = str2[i];
    }
    unordered_set<char> s2(str2.begin(), str2.end());
    return s2.size() < 26;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func canConvert(str1, str2 string) bool {
    if str1 == str2 { return true }
    mp := map[byte]byte{}
    for i := 0; i < len(str1); i++ {
        if v, ok := mp[str1[i]]; ok && v != str2[i] {
            return false
        }
        mp[str1[i]] = str2[i]
    }
    s2 := map[byte]struct{}{}
    for i := 0; i < len(str2); i++ {
        s2[str2[i]] = struct{}{}
    }
    return len(s2) < 26
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

import java.util.*;
class Solution {
    public boolean canConvert(String str1, String str2) {
        if (str1.equals(str2)) return true;
        Map<Character, Character> map = new HashMap<>();
        for (int i = 0; i < str1.length(); i++) {
            char c1 = str1.charAt(i), c2 = str2.charAt(i);
            if (map.containsKey(c1) && map.get(c1) != c2) return false;
            map.put(c1, c2);
        }
        Set<Character> set = new HashSet<>();
        for (char c : str2.toCharArray()) set.add(c);
        return set.size() < 26;
    }
}
1
2
3
4
5
6
7
8
9

fun canConvert(str1: String, str2: String): Boolean {
    if (str1 == str2) return true
    val map = mutableMapOf<Char, Char>()
    for (i in str1.indices) {
        if (map.containsKey(str1[i]) && map[str1[i]] != str2[i]) return false
        map[str1[i]] = str2[i]
    }
    return str2.toSet().size < 26
}
1
2
3
4
5
6
7
8
9

def canConvert(str1: str, str2: str) -> bool:
    if str1 == str2:
        return True
    mp = {}
    for a, b in zip(str1, str2):
        if a in mp and mp[a] != b:
            return False
        mp[a] = b
    return len(set(str2)) < 26
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

use std::collections::{HashMap, HashSet};
pub fn can_convert(str1: String, str2: String) -> bool {
    if str1 == str2 { return true; }
    let mut mp = HashMap::new();
    let s1 = str1.as_bytes();
    let s2 = str2.as_bytes();
    for i in 0..s1.len() {
        if let Some(&v) = mp.get(&s1[i]) {
            if v != s2[i] { return false; }
        }
        mp.insert(s1[i], s2[i]);
    }
    let set: HashSet<u8> = s2.iter().cloned().collect();
    set.len() < 26
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

function canConvert(str1: string, str2: string): boolean {
    if (str1 === str2) return true;
    const mp = new Map<string, string>();
    for (let i = 0; i < str1.length; i++) {
        if (mp.has(str1[i]) && mp.get(str1[i]) !== str2[i]) return false;
        mp.set(str1[i], str2[i]);
    }
    const set = new Set(str2);
    return set.size < 26;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)