Determine if Two Strings Are Close

Med

#1521Time: 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.1 company

Patterns

Algorithms

Data structures

Companies

Prompt

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 <= 10⁵
word1 and word2 contain only lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

The logic for this problem boils down to two key conditions that must be met for two strings to be considered 'close':

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.
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.

1class Solution {2    public boolean closeStrings(String word1, String word2) {3        if (word1.length() != word2.length()) {4            return false;5        }6 7        Map<Character, Integer> freq1 = new HashMap<>();8        for (char c : word1.toCharArray()) {9            freq1.put(c, freq1.getOrDefault(c, 0) + 1);10        }11 12        Map<Character, Integer> freq2 = new HashMap<>();13        for (char c : word2.toCharArray()) {14            freq2.put(c, freq2.getOrDefault(c, 0) + 1);15        }16 17        if (!freq1.keySet().equals(freq2.keySet())) {18            return false;19        }20 21        List<Integer> freqsList1 = new ArrayList<>(freq1.values());22        List<Integer> freqsList2 = new ArrayList<>(freq2.values());23 24        Collections.sort(freqsList1);25        Collections.sort(freqsList2);26 27        return freqsList1.equals(freqsList2);28    }29}

Complexity

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.

Trade-offs

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.

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.

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)).

Walkthrough

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.

1class Solution {2    public boolean closeStrings(String word1, String word2) {3        if (word1.length() != word2.length()) {4            return false;5        }6 7        int[] freq1 = new int[26];8        int[] freq2 = new int[26];9        for (int i = 0; i < word1.length(); i++) {10            freq1[word1.charAt(i) - 'a']++;11            freq2[word2.charAt(i) - 'a']++;12        }13 14        // Check if the set of characters is the same15        for (int i = 0; i < 26; i++) {16            if ((freq1[i] == 0 && freq2[i] > 0) || (freq1[i] > 0 && freq2[i] == 0)) {17                return false;18            }19        }20 21        // Check if the frequency of frequencies is the same22        Arrays.sort(freq1);23        Arrays.sort(freq2);24 25        return Arrays.equals(freq1, freq2);26    }27}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class 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 ); } }

1class 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 ())

1class 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 ); } };

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem