1657. Determine if Two Strings Are Close

Description

Given two strings, the task is to determine whether they are "close." Two strings are considered close if you can transform one string into the other by using the following operations any number of times:

1. Swap any two existing characters.
2. Transform every occurrence of one existing character into another existing character and do the same with the other character.

The strings must contain the same unique characters with the same frequency (though possibly in a different order) to be close.

Intuition

To determine if two strings are close, we need to focus on two main aspects:

1. Both strings must contain the exact same set of unique characters.
2. The frequency distribution of characters in both strings must be the same, though the characters themselves can differ.

Approach

1. Check Unique Characters: First, check if both strings contain the same set of unique characters. If not, they cannot be close.
2. Check Frequency Distribution: Calculate the frequency of each character in both strings. Sort these frequencies and compare them. If they match, the strings are close; otherwise, they are not.

Complexity

Time Complexity:

The time complexity is O(n log n), where n is the length of the strings. This comes from the need to sort the frequency lists and check the unique characters.

Space Complexity:

The space complexity is O(1) if we only consider extra space needed for frequency counts and sets, and O(n) if we consider the storage of characters and their frequencies.

Code

C++

class Solution {
public:
    bool checkIsUnique(unordered_set& set1, unordered_set& set2) {
        for (char c : set1) {
            if (set2.find(c) == set2.end()) return false;
        }
        return true;
    }

    bool FrequencyOfChars(unordered_map& word1, unordered_map& word2) {
        vector one, two;

        for (auto& [key, value] : word1) {
            one.push_back(value);
        }
        for (auto& [key, value] : word2) {
            two.push_back(value);
        }

        sort(one.begin(), one.end());
        sort(two.begin(), two.end());

        if (one.size() != two.size()) return false;

        for (size_t i = 0; i < one.size(); i++) {
            if (one[i] != two[i]) return false;
        }
        return true;
    }

    bool closeStrings(string word1, string word2) {
        if (word1.length() != word2.length()) return false;

        unordered_map Map1, Map2;

        for (size_t i = 0; i < word1.length(); i++) {
            Map1[word1[i]]++;
            Map2[word2[i]]++;
        }

        unordered_set uniqueWord1(word1.begin(), word1.end());
        unordered_set uniqueWord2(word2.begin(), word2.end());

        if (!checkIsUnique(uniqueWord1, uniqueWord2)) return false;

        return FrequencyOfChars(Map1, Map2);
    }
};

Python

class Solution:
    def checkIsUnique(self, set1, set2):
        for c in set1:
            if c not in set2:
                return False
        return True

    def FrequencyOfChars(self, word1, word2):
        one = sorted(word1.values())
        two = sorted(word2.values())
        
        if len(one) != len(two):
            return False

        for i in range(len(one)):
            if one[i] != two[i]:
                return False
        return True

    def closeStrings(self, word1: str, word2: str) -> bool:
        if len(word1) != len(word2):
            return False

        Map1 = {}
        Map2 = {}

        for i in range(len(word1)):
            Map1[word1[i]] = Map1.get(word1[i], 0) + 1
            Map2[word2[i]] = Map2.get(word2[i], 0) + 1

        uniqueWord1 = set(word1)
        uniqueWord2 = set(word2)

        if not self.checkIsUnique(uniqueWord1, uniqueWord2):
            return False

        return self.FrequencyOfChars(Map1, Map2)

Java

public class Solution {
    private boolean checkIsUnique(Set set1, Set set2) {
        for (char c : set1) {
            if (!set2.contains(c)) return false;
        }
        return true;
    }

    private boolean FrequencyOfChars(Map word1, Map word2) {
        List one = new ArrayList<>(word1.values());
        List two = new ArrayList<>(word2.values());

        Collections.sort(one);
        Collections.sort(two);

        for (int i = 0; i < one.size(); i++) {
            if (!one.get(i).equals(two.get(i))) return false;
        }
        return true;
    }

    public boolean closeStrings(String word1, String word2) {
        if (word1.length() != word2.length()) return false;

        Map Map1 = new HashMap<>();
        Map Map2 = new HashMap<>();

        for (int i = 0; i < word1.length(); i++) {
            Map1.put(word1.charAt(i), Map1.getOrDefault(word1.charAt(i), 0) + 1);
            Map2.put(word2.charAt(i), Map2.getOrDefault(word2.charAt(i), 0) + 1);
        }

        Set uniqueWord1 = new HashSet<>(word1.chars().mapToObj(c -> (char) c).toList());
        Set uniqueWord2 = new HashSet<>(word2.chars().mapToObj(c -> (char) c).toList());

        if (!checkIsUnique(uniqueWord1, uniqueWord2)) return false;

        return FrequencyOfChars(Map1, Map2);
    }
}

JavaScript

var closeStrings = (word1,word2) => {
    if(word1.length != word2.length) return false

    const Map1 = {}
    const Map2 = {}
    for(let i = 0 ; i a-b)
    let two = Object.values(word2).sort((a,b) => a-b)
    console.log(one,two)
    for(let i = 0 ; i < one.length ; i++){
        if(one[i] != two[i]) return false
    }
    return true
}