{x}
blog image

Determine if Two Strings Are Close

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.

Solution Explanation: Determine if Two Strings Are Close

This problem asks whether two strings, word1 and word2, can be made identical through a series of character swaps and character transformations. The core idea is that two strings are considered "close" if they satisfy two conditions:

  1. Same character types: Both strings must contain the same set of characters (though the frequency of each character might differ).
  2. Same character frequency distribution (after sorting): If we sort the frequencies of each character in both strings, the sorted frequency arrays must be identical.

The solution employs a counting approach, leveraging either hash tables (dictionaries in Python) or arrays to efficiently count character frequencies.

Algorithm:

  1. Character Counting:

    • Create frequency counters (dictionaries or arrays of size 26 for lowercase English letters) for both word1 and word2. These counters store the number of times each character appears in each string.

  2. Character Type Check:

    • Compare the sets of characters present in the frequency counters. If the sets are different (meaning one string has a character the other doesn't), the strings cannot be close, and we return false.

  3. Frequency Sorting and Comparison:

    • Extract the frequency values from the counters (values from dictionaries or array elements).
    • Sort these frequency lists in ascending order.
    • Compare the sorted frequency lists. If they are not identical, the strings are not close, and we return false.

  4. Return True:

    • If both the character type check and the sorted frequency comparison pass, it means the strings can be made identical using the allowed operations, and we return true.

Time and Space Complexity:

  • Time Complexity: O(m + n + C log C), where m and n are lengths of word1 and word2, and C is the number of unique characters (26 in this case). The dominant factors are counting characters (O(m+n)), sorting frequencies (O(C log C)), and comparing sets/arrays (O(C)).

  • Space Complexity: O(C), dominated by the space used for frequency counters. In the worst case (all 26 letters present), we need space proportional to the alphabet size.

Code Implementation (Python):

from collections import Counter
 
def closeStrings(word1: str, word2: str) -> bool:
    """
    Checks if two strings are "close" based on character swaps and transformations.
    """
    count1 = Counter(word1)
    count2 = Counter(word2)
 
    # Check if character sets are the same
    if set(count1.keys()) != set(count2.keys()):
        return False
 
    # Sort frequency lists and compare
    sorted_freq1 = sorted(count1.values())
    sorted_freq2 = sorted(count2.values())
    return sorted_freq1 == sorted_freq2

The code in other languages (Java, C++, Go, TypeScript, Rust) follows a very similar logic, adapting the data structures and functions for character counting and sorting according to the language's specifics. The overall algorithmic approach remains consistent across all implementations.