Vultr DocsLatest Content

Determine if Two Strings Are Close

Updated on 22 May, 2025
Determine if Two Strings Are Close header image

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

  • C++
  • Java
cpp 
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;
    }
};

This solution addresses the problem of determining if two strings, str1 and str2, are "close," which involves checking several conditions based on the characters' frequency and the types of characters used in both strings. The solution is implemented in C++ and encapsulated in a class method areCloseStrings.

  • Begin by comparing the sizes of str1 and str2. If they differ, the function immediately returns false indicating the strings are not close.
  • Use two vectors, count1 and count2, initialized to size 26 (corresponding to the letters a-z) with all values set to 0. These vectors count the frequency of each character in str1 and str2 respectively.
  • Two integer variables, bitmask1 and bitmask2, are used to store a bitmask that represents the unique characters present in str1 and str2. As you iterate over each character in the strings, update the respective character's frequency in the count vectors and update the bitmask using bitwise OR operation.
  • After processing each string, compare bitmask1 and bitmask2. If they differ, return false as this implies the sets of characters in the strings are different.
  • Sort both count1 and count2. This is to prepare for a position-by-position comparison of the frequency of characters.
  • Finally, iterate over the sorted count vectors. If any position differs, return false, otherwise, after the loop, return true indicating the strings are close according to the given conditions.

By efficiently using bitmasking for character set comparison and sorting for frequency matching, the solution ensures that two strings are close only when they share identical character sets and the characters can be rearranged to match each other’s frequencies.

java 
class Comparator {

    public boolean areWordsEquivalent(String str1, String str2) {
        if (str1.length() != str2.length()) {
            return false;
        }
        int count1[] = new int[26];
        int count2[] = new int[26];
        int bitmask1 = 0;
        int bitmask2 = 0;
        for (char ch : str1.toCharArray()) {
            count1[ch - 'a']++;
            bitmask1 |= (1 << (ch - 'a'));
        }
        for (char ch : str2.toCharArray()) {
            count2[ch - 'a']++;
            bitmask2 |= (1 << (ch - 'a'));
        }
        if (bitmask1 != bitmask2) {
            return false;
        }
        Arrays.sort(count1);
        Arrays.sort(count2);
        for (int idx = 0; idx < 26; idx++) {
            if (count1[idx] != count2[idx]) {
                return false;
            }
        }
        return true;
    }
}

This solution in Java determines if two strings are close based on specific criteria. The method areWordsEquivalent checks if both strings have the same length, characters, and frequency of characters, but not necessarily in the same order.

Understand the step-by-step approach used:

  1. Check if str1 and str2 are of the same length. If not, return false immediately.
  2. Initialize two frequency arrays count1 and count2 for each character, and two bitmasks bitmask1 and bitmask2 to track the unique characters.
  3. Iterate over each character in str1:
    • Increment the corresponding index in count1.
    • Update bitmask1 to include the current character.
  4. Repeat the process for str2 using count2 and bitmask2.
  5. Compare bitmask1 and bitmask2. If they differ, the sets of characters in the strings are different, and return false.
  6. Sort both count1 and count2.
  7. Compare the sorted arrays. If any corresponding frequency counts differ, return false, indicating the strings are not close.
  8. If all checks pass, return true, indicating the strings are close.

This method effectively uses character frequencies and bit manipulation to ensure both strings contain exactly the same characters with the same frequencies, hence determining if they are "close" by the specified problem's definition.

Comments

No comments yet.