1153. String Transforms Into Another String

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.

• Time : O(k^2)
• Space : O(k)

class Solution {
    bool allSame(unordered_map<char,char> ch) {
        for(auto [from, to] : ch) {
            if(from != to) return false;
        }
        return true;
    }
public:
    bool canConvert(string str1, string str2) {
        unordered_map<char,char> convert;
        for(int i = 0; i < str1.length(); i++) {
            if(convert.count(str1[i])) {
                if(convert[str1[i]] != str2[i]) return false;
            } else convert[str1[i]] = str2[i];
        }
        if(convert.size() < 26) return true;
        
        for(char ch = 'a'; ch <= 'z'; ch++) {
            for(char ch2 = ch + 1; ch2 <= 'z'; ch2++) {
                if(convert[ch] == convert[ch2]) return true;
            }
        }
        
        for(int i = 0; i < 26; i++) {
            bool removedCycle = false;
            for(char ch = 'a'; ch <= 'z'; ch++) {
                if(!convert.count(ch) || convert[ch] == ch) continue;
                char to = convert[ch];
                if(convert.count(to) and convert[to] != to) continue;
                convert[to] = to;
                convert.erase(ch);
                removedCycle = true;
            }
            if(!removedCycle) break;
        }

        return allSame(convert);
    }
};