SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

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<char>& set1, unordered_set<char>& set2) {
        for (char c : set1) {
            if (set2.find(c) == set2.end()) return false;
        }
        return true;
    }

    bool FrequencyOfChars(unordered_map<char, int>& word1, unordered_map<char, int>& word2) {
        vector<int> 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<char, int> Map1, Map2;

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

        unordered_set<char> uniqueWord1(word1.begin(), word1.end());
        unordered_set<char> 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<Character> set1, Set<Character> set2) {
        for (char c : set1) {
            if (!set2.contains(c)) return false;
        }
        return true;
    }

    private boolean FrequencyOfChars(Map<Character, Integer> word1, Map<Character, Integer> word2) {
        List<Integer> one = new ArrayList<>(word1.values());
        List<Integer> 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<Character, Integer> Map1 = new HashMap<>();
        Map<Character, Integer> 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<Character> uniqueWord1 = new HashSet<>(word1.chars().mapToObj(c -> (char) c).toList());
        Set<Character> 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<word1.length ; i++){
        if(Map1[word1[i]]){
            Map1[word1[i]]++
        }else{
            Map1[word1[i]] = 1
        }

        if(Map2[word2[i]]){
            Map2[word2[i]]++
        }else{
            Map2[word2[i]] = 1
        }
        
    }

    const uniqueWord1 = new Set(word1)
    const uniqueWord2 = new Set(word2)

    if(!checkIsUnique(uniqueWord1,uniqueWord2)) return false
    // console.log(checkIsUnique(uniqueWord1,uniqueWord2))
    return FrequencyOfChars(Map1,Map2)  
}
function checkIsUnique(set1,set2){
    for(let i of set1){
        if(!set2.has(i)) return false
    }
    return true
}
function FrequencyOfChars (word1,word2) {
    let one = Object.values(word1).sort((a,b) => 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
}