1657. Determine if Two Strings Are Close

T: O(nlogn), n = 26
S: O(n)

```java
class Solution {
    public boolean closeStrings(String word1, String word2) {
        // first check length if word1.len != word2.len -> return false
        if (word1.length() != word2.length()) {
            return false;
        }
        Map<Character, Integer> freq1 = new HashMap<>();
        Map<Character, Integer> freq2 = new HashMap<>();
        for (int i = 0; i < word1.length(); i++) {
            char c1 = word1.charAt(i);
            freq1.put(c1, freq1.getOrDefault(c1, 0)+1);

            char c2 = word2.charAt(i);
            freq2.put(c2, freq2.getOrDefault(c2, 0)+1);
        }
        // for sort, so I add to list
        List<Integer> list1 = new ArrayList<>();
        for (Character c1 : freq1.keySet()) {
            // second check is char has same char appearing in both words, if not -> return false
            if (!freq2.containsKey(c1)) {
                return false;
            }
            list1.add(freq1.get(c1));
        }
        List<Integer> list2 = new ArrayList<>();
        for (Character c2 : freq2.keySet()) {
            list2.add(freq2.get(c2));
        }
        // last sort freq count -> if both char count(don't care the char, only care count) match 
        Collections.sort(list1);
        Collections.sort(list2);

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

/*
first check length if word1.len != word2.len -> return false
second check is char has same char appearing in both words, if not -> return false

last sort freq count -> if both char count(don't care the char, only care count) match 
T: O(nlogn)
S: O(n)



if use dfs? too hard

word1 = "cabbba", 
word2 = "abbccc"

122333
word2 = "abbccc"
         
         122333
         312221
word1 = "cabbba"


         122333
         312221
         make
         311222
         133222
         122333   

         so seems we only care the count and freq, position not important!
*/
```

using array is easier because only has 26 lowercase char

```java
class Solution {
    public boolean closeStrings(String word1, String word2) {
        // first check length if word1.len != word2.len -> return false
        if (word1.length() != word2.length()) {
            return false;
        }
        int[] freq1 = new int[26];
        int[] freq2 = new int[26];
        for (int i = 0; i < word1.length(); i++) {
            freq1[word1.charAt(i) - 'a']++;
            freq2[word2.charAt(i) - 'a']++;
        }
        
        // second check is char has same char appearing in both words, if not -> return false
        for (int i = 0; i < 26; i++) {
            if (freq1[i] != 0 && freq2[i] == 0 || freq1[i] == 0 && freq2[i] != 0) {
                return false;
            }
        }
        // last sort freq count -> if both char count(don't care the char, only care count) match 
        Arrays.sort(freq1);
        Arrays.sort(freq2);

        for (int i = 0; i < 26; i++) {
            if (freq1[i] != freq2[i]) {
                return false;
            }
        }
        return true;
    }
}
```

using bucket sort O(n)

```java
class Solution {
    public boolean closeStrings(String word1, String word2) {
        // first check length if word1.len != word2.len -> return false
        if (word1.length() != word2.length()) {
            return false;
        }
        int[] freq1 = new int[26];
        int[] freq2 = new int[26];
        for (int i = 0; i < word1.length(); i++) {
            freq1[word1.charAt(i) - 'a']++;
            freq2[word2.charAt(i) - 'a']++;
        }
        
        // second check is char has same char appearing in both words, if not -> return false
        for (int i = 0; i < 26; i++) {
            if (freq1[i] != 0 && freq2[i] == 0 || freq1[i] == 0 && freq2[i] != 0) {
                return false;
            }
        }

        // without sorting, using bucket sort
        int n = word1.length();
        int[] countBucket1 = new int[n+1];
        int[] countBucket2 = new int[n+1];
        for (int i = 0; i < 26; i++) {
            countBucket1[freq1[i]]++;
            countBucket2[freq2[i]]++;
        }

        for (int i = 0; i < countBucket1.length; i++) {
            if (countBucket1[i] != countBucket2[i]) {
                return false;
            }
        }
        return true;
    }
}
```