Determine if Two Strings Are Close

Problem Statement

Two strings are deemed close if they can be transformed into one another through a series of character operations. Specifically, there are two types of permissible operations:

1. Swapping any two existing characters: For instance, transforming abcde to aecdb by swapping b with e.
2. Transforming every occurrence of one character into another across the entire string (reciprocal transformation of both characters is mandatory): For example, changing aacabb to bbcbaa involves converting all occurrences of a to b and vice versa.

Both operations can be repeatedly applied to either of the strings to achieve similarity. The challenge is to determine whether one string can be transformed into the other by these operations, returning true if so, and false otherwise.

Examples

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.

Approach and Intuition

Given the operations allowed:

• Operation 1 (Swapping characters): This operation indicates that the order of characters can effectively be ignored, as any character can be moved to any position.
• Operation 2 (Transforming characters mutually): This key operation allows for the transformation of the frequency of characters, provided they can be mapped in pairs.

From these operations, a few fundamental conditions must be met for two strings, word1 and word2, to be considered close:

1. Same characters with the same frequency set: Both strings should have the exact set of characters and the same set of frequencies for those characters, though the characters themselves need not necessarily map 1-to-1 in frequency.
2. Permutations with potential frequency swaps: Given their set of character frequencies, one should be a permutation of the other.

From the examples:

• Example 1: ("abc" to "bca") demonstrates that we can reorder word1 to look exactly like word2 using operations primarily focusing on the position of characters.
• Example 2: Shows a scenario where no number of operations can increase the count of a non-existent character ("a" to "aa").
• Example 3: Highlights a more complex transformation where both character reordering and multiple mutual transformations (swapping frequencies) yield a successful transition from word1 to word2.

To programmatically determine if two strings are close:

1. Check Character Existence: Ensure both strings contain exactly the same characters.
2. Frequency Match: Validate that the frequencies of these characters (i.e., how many times each character appears) can form the same multiset.

This approach directly leverages the described operations to validate the closeness of two strings based on character content and frequency, rather than their specific ordering or direct character-to-character mapping.

Solutions

class Solution {
public:
    bool areCloseStrings(string str1, string str2) {
        if (str1.size() != str2.size()) return false;
        vector<int> count1(26, 0);
        vector<int> count2(26, 0);
        int bitmask1 = 0;
        int bitmask2 = 0;
        for (auto ch : str1) {
            count1[ch - 'a']++;
            bitmask1 |= (1 << (ch - 'a'));
        }
        for (auto ch : str2) {
            count2[ch - 'a']++;
            bitmask2 |= (1 << (ch - 'a'));
        }
        if (bitmask1 != bitmask2) return false;
    
        sort(count1.begin(), count1.end());
        sort(count2.begin(), count2.end());
    
        for (int idx = 0; idx < 26; idx++) {
            if (count1[idx] != count2[idx]) return false;
        }
        return true;
    }
};