# Determine if Two Strings Are Close
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/determine-if-two-strings-are-close)
Canonical: https://scaleengineer.com/dsa/problems/determine-if-two-strings-are-close
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Hash Table, String
**Companies:** [Postmates](https://scaleengineer.com/companies/postmates)
---
## Problem
Two strings are considered **close** if you can attain one from the other using the following operations:

* Operation 1: Swap any two **existing** characters.  
  * For example, `abcde -> aecdb`
* Operation 2: Transform **every** occurrence of one **existing** character into another **existing** character, and do the same with the other character.  
  * For example, `aacabb -> bbcbaa` (all `a`'s turn into `b`'s, and all `b`'s turn into `a`'s)

You can use the operations on either string as many times as necessary.

Given two strings, `word1` and `word2`, return `true` _if_ `word1` _and_ `word2` _are **close**, and_ `false` _otherwise._

**Example 1:**

**Input:** word1 = "abc", word2 = "bca"
**Output:** true
**Explanation:** You can attain word2 from word1 in 2 operations.
Apply Operation 1: "abc" -> "acb"
Apply Operation 1: "acb" -> "bca"

**Example 2:**

**Input:** word1 = "a", word2 = "aa"
**Output:** false
**Explanation:** It is impossible to attain word2 from word1, or vice versa, in any number of operations.

**Example 3:**

**Input:** word1 = "cabbba", word2 = "abbccc"
**Output:** true
**Explanation:** You can attain word2 from word1 in 3 operations.
Apply Operation 1: "cabbba" -> "caabbb"
Apply Operation 2: "caabbb" -> "baaccc"
Apply Operation 2: "baaccc" -> "abbccc"

**Constraints:**

* `1 <= word1.length, word2.length <= 105`
* `word1` and `word2` contain only lowercase English letters.

# Approaches
## HashMap and Sorting
This approach uses HashMaps to count character frequencies and then compares the properties of these maps to determine if the strings are close. It's a straightforward implementation of the logical conditions derived from the problem statement.
**Time:** O(N + K log K), where N is the length of the strings and K is the number of unique characters. Since K is at most 26 for this problem, the complexity is effectively O(N). · **Space:** O(K), where K is the number of unique characters. This space is used for the HashMaps and the lists of frequencies. For this problem, K ≤ 26.
**Pros:** Conceptually straightforward, directly mapping characters to their counts.; Flexible and works for any character set, not just lowercase English letters.
**Cons:** Slightly higher overhead and memory usage compared to an array-based approach due to object creation (for keys and values) and hash computations.; Can be slower in practice due to poorer cache locality.
### Explanation
The logic for this problem boils down to two key conditions that must be met for two strings to be considered 'close':

1.  **They must have the same set of unique characters.** Operation 1 (swapping characters) and Operation 2 (transforming one character to another) do not introduce new character types or eliminate existing ones from the set of characters in a string.
2.  **They must have the same multiset of character frequencies.** Operation 1 only rearranges characters, leaving frequencies unchanged. Operation 2 allows swapping the frequencies between two characters (e.g., all 'a's become 'b's and all 'b's become 'a's), but the collection of frequency counts itself remains the same. For example, a string with character counts `{2, 5, 8}` can be transformed into another string with counts `{2, 5, 8}`, but not one with counts `{1, 6, 8}`.

This approach implements these checks using HashMaps.

- First, we perform a basic check: if the lengths of `word1` and `word2` are different, they can never be close, so we return `false`.
- We then create two HashMaps, `freq1` and `freq2`, to store the frequency of each character for `word1` and `word2`, respectively.
- We check the first condition by comparing the key sets of the two maps. If `freq1.keySet()` is not equal to `freq2.keySet()`, they don't have the same characters, and we return `false`.
- To check the second condition, we extract the frequency values from both maps into two separate lists. We sort these lists and then compare them. If the sorted lists are identical, it means they have the same multiset of frequencies.

If both conditions are satisfied, we return `true`.

```java
class Solution {
    public boolean closeStrings(String word1, String word2) {
        if (word1.length() != word2.length()) {
            return false;
        }

        Map<Character, Integer> freq1 = new HashMap<>();
        for (char c : word1.toCharArray()) {
            freq1.put(c, freq1.getOrDefault(c, 0) + 1);
        }

        Map<Character, Integer> freq2 = new HashMap<>();
        for (char c : word2.toCharArray()) {
            freq2.put(c, freq2.getOrDefault(c, 0) + 1);
        }

        if (!freq1.keySet().equals(freq2.keySet())) {
            return false;
        }

        List<Integer> freqsList1 = new ArrayList<>(freq1.values());
        List<Integer> freqsList2 = new ArrayList<>(freq2.values());

        Collections.sort(freqsList1);
        Collections.sort(freqsList2);

        return freqsList1.equals(freqsList2);
    }
}
```
### Algorithm
- Check if `word1.length()` is different from `word2.length()`. If so, return `false`.
- Create two `HashMap<Character, Integer>` to store character frequencies for each string.
- Populate the maps by iterating through each string.
- Compare the key sets of the two maps. If they are not identical, return `false`.
- Extract the frequency values from both maps into two lists.
- Sort both lists of frequencies.
- Compare the sorted lists. If they are identical, return `true`; otherwise, return `false`.

## Frequency Array and Sorting
This is a highly optimized approach that leverages the problem constraint that the strings only contain lowercase English letters. It uses fixed-size arrays as frequency maps, which is faster and more memory-efficient than using HashMaps.
**Time:** O(N), where N is the length of the strings. Populating the arrays takes O(N) time. All subsequent steps (checking character sets, sorting, and comparing arrays) take constant time because the array size is fixed at 26. · **Space:** O(1). The space required for the two frequency arrays is constant (2 * 26 * 4 bytes) and does not depend on the length of the input strings.
**Pros:** Extremely efficient in both time and space.; Uses primitive arrays, avoiding object overhead and leveraging cache-friendliness.; Constant space complexity, independent of input size.
**Cons:** This specific implementation is tailored to a fixed, small character set (lowercase English letters). It would need modification for larger or different character sets.
### Explanation
This approach follows the same core logic as the HashMap approach but uses a more efficient data structure. The conditions for two strings being 'close' remain the same: same length, same set of characters, and same multiset of frequencies.

- The initial length check is identical: if lengths differ, return `false`.
- Instead of HashMaps, we use two integer arrays of size 26, `freq1` and `freq2`, to store character counts. The index `i` in the array corresponds to the `i`-th letter of the alphabet (e.g., index 0 for 'a', 1 for 'b', etc.). We can populate both arrays in a single pass since the strings are of equal length.
- To verify that the character sets are identical, we iterate through the 26 positions of the arrays. If we find an index `i` where one array has a positive count (`freq1[i] > 0`) and the other has zero (`freq2[i] == 0`), it means one string contains a character that the other lacks. In this case, we return `false`.
- To verify that the frequency distributions are the same, we sort both frequency arrays. Sorting arranges the counts in non-decreasing order. If the original strings are close, their sorted frequency arrays will be identical. For example, counts `{a:3, b:1}` and `{c:1, d:3}` both result in a sorted frequency array of `[..., 0, ..., 1, 3]`. We use `Arrays.equals()` to compare the sorted arrays.

This method is significantly faster in practice due to the use of primitive arrays, which avoids object overhead and benefits from better memory locality.

```java
class Solution {
    public boolean closeStrings(String word1, String word2) {
        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']++;
        }

        // Check if the set of characters is the same
        for (int i = 0; i < 26; i++) {
            if ((freq1[i] == 0 && freq2[i] > 0) || (freq1[i] > 0 && freq2[i] == 0)) {
                return false;
            }
        }

        // Check if the frequency of frequencies is the same
        Arrays.sort(freq1);
        Arrays.sort(freq2);

        return Arrays.equals(freq1, freq2);
    }
}
```
### Algorithm
- Check if `word1.length()` is different from `word2.length()`. If so, return `false`.
- Create two integer arrays, `freq1` and `freq2`, of size 26, initialized to zeros.
- Iterate from `i = 0` to `word1.length() - 1`, incrementing the counts in `freq1` and `freq2` for the characters at `word1.charAt(i)` and `word2.charAt(i)`.
- Iterate through the frequency arrays from index 0 to 25. If a character exists in one string but not the other (`(freq1[i] > 0 && freq2[i] == 0) || ...`), return `false`.
- Sort both `freq1` and `freq2` arrays.
- Return the result of comparing the two sorted arrays for equality (`Arrays.equals(freq1, freq2)`).

# Solutions
### Java

```java
class Solution { public boolean closeStrings ( String word1 , String word2 ) { int [] cnt1 = new int [ 26 ]; int [] cnt2 = new int [ 26 ]; for ( int i = 0 ; i < word1 . length (); ++ i ) { ++ cnt1 [ word1 . charAt ( i ) - 'a' ]; } for ( int i = 0 ; i < word2 . length (); ++ i ) { ++ cnt2 [ word2 . charAt ( i ) - 'a' ]; } for ( int i = 0 ; i < 26 ; ++ i ) { if (( cnt1 [ i ] == 0 ) != ( cnt2 [ i ] == 0 )) { return false ; } } Arrays . sort ( cnt1 ); Arrays . sort ( cnt2 ); return Arrays . equals ( cnt1 , cnt2 ); } }
```

### Python

```python
class Solution : def closeStrings ( self , word1 : str , word2 : str ) -> bool : cnt1 , cnt2 = Counter ( word1 ), Counter ( word2 ) return sorted ( cnt1 . values ()) == sorted ( cnt2 . values ()) and set ( cnt1 . keys () ) == set ( cnt2 . keys ())
```

### CPP

```cpp
class Solution { public: bool closeStrings ( string word1 , string word2 ) { int cnt1 [ 26 ]{}; int cnt2 [ 26 ]{}; for ( char & c : word1 ) { ++ cnt1 [ c - 'a' ]; } for ( char & c : word2 ) { ++ cnt2 [ c - 'a' ]; } for ( int i = 0 ; i < 26 ; ++ i ) { if (( cnt1 [ i ] == 0 ) != ( cnt2 [ i ] == 0 )) { return false ; } } sort ( cnt1 , cnt1 + 26 ); sort ( cnt2 , cnt2 + 26 ); return equal ( cnt1 , cnt1 + 26 , cnt2 ); } };
```