1657. Determine if Two Strings Are Close
Problem Description
The problem introduces a concept called "close" strings. Two strings are "close" if one can be obtained from the other by performing any of the following operations, any number of times:
- Operation 1: Swap any two existing characters in the string. For example, changing "abce" to "aebc" by swapping 'b' with 'e'.
- Operation 2: Transform every occurrence of one existing character into another existing character and vice versa. For instance, changing "aacabb" to "bbcbaa" by swapping all 'a' characters with 'b' characters, and all 'b' characters with 'a' characters.
The goal is to determine if two given strings, word1
and word2
, can be considered "close" by applying these operations.
Intuition
To solve this problem, we need to understand that the operations allowed don't change the frequency of characters, only their positions or representations. Therefore, two "close" strings must have the same set of characters and the same frequency of each character, although the characters themselves can be different.
The crucial realization is that operation 1 allows us to reorder characters in any fashion, making the relative order of characters inconsequential. Operation 2 allows us to transform characters into each other, given that both characters exist in both strings. The consequence of this is:
- Both
word1
andword2
must contain the same unique characters - they must have the same set of keys in their character counts (Counter). - Both
word1
andword2
must have the same character frequencies, which implies, after sorting their frequency counts, these should match.
With these constraints in mind, the solution approach is to count the frequency of each character in word1
and word2
using Python's Counter
, then compare the sorted values of the counters to check for matching frequencies, as well as compare the sets of keys to ensure that both words contain the same unique characters.
If both the sorted values of the counts and the sets of unique characters match, we return true
. Otherwise, we return false
.
Learn more about Sorting patterns.
Solution Approach
The solution takes the following approach:
-
Use Python's
Counter
from thecollections
module to count the frequency of each character in bothword1
andword2
.Counter
is a dictionary subclass that's designed to count hashable objects. It's a collection where elements are stored as dictionary keys and their counts are stored as dictionary values. -
Check if the set of keys from both Counters is the same—
set(cnt1.keys()) == set(cnt2.keys())
. This checks whetherword1
andword2
contain exactly the same unique characters. This is a requirement because operation 2 can only be performed if a character exists in both strings. -
Compare the sorted values of both counters—
sorted(cnt1.values()) == sorted(cnt2.values())
. This step checks ifword1
andword2
have the same frequency of characters (the same count of each character). Sorting is crucial here since we need to compare frequencies regardless of the character they are associated with.
If both conditions are met, then word1
and word2
are "close", and the function returns True
. If any of the conditions is not met, the function returns False
. These comparisons effectively implement the constraints of the two operations without having to manually perform the operations themselves.
Here's a step-by-step breakdown of how the provided solution achieves this:
1class Solution:
2 def closeStrings(self, word1: str, word2: str) -> bool:
3 # Count the frequency of each character in both words
4 cnt1, cnt2 = Counter(word1), Counter(word2)
5
6 # If the sets of unique characters (keys of the counters) are the same and
7 # the sorted lists of character counts (values of the counters) are the same,
8 # then the strings are "close"
9 return sorted(cnt1.values()) == sorted(cnt2.values()) and set(cnt1.keys()) == set(cnt2.keys())
The algorithmic complexity of this solution is mainly dependent on the sorting of the counted values, which is O(n log n) where n is the number of unique characters. Comparing the sets of keys essentially happens in linear time, O(m), where m is the length of the string.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take an example to illustrate the solution approach with two strings, word1 = "baba" and word2 = "abab".
-
We first count the frequency of each character in both words. The
Counter
forword1
is{ 'b': 2, 'a': 2 }
and forword2
is{ 'a': 2, 'b': 2 }
. This shows that both 'a' and 'b' appear twice in both strings. -
We then compare the sets of keys from both dictionaries—
set(cnt1.keys()) == set(cnt2.keys())
. For our example, this means comparing{ 'b', 'a' } == { 'a', 'b' }
, which evaluates toTrue
because the set operation takes care of the order, and both sets contain the same elements. -
For the final step, we compare the sorted values of both counters—
sorted(cnt1.values()) == sorted(cnt2.values())
. In this case,sorted([2, 2]) == sorted([2, 2])
. The sorted list of character counts for bothword1
andword2
is[2, 2]
, which means that both strings have the same frequency for their characters.
Since both conditions are satisfied, we conclude that word1 and word2 are indeed "close" as per the problem's definition. The function would return True
.
In a case where word1 = "baba" and word2 = "abbc", this is how the approach would result in a False
:
-
Counter(word1)
gives{ 'b': 2, 'a': 2 }
andCounter(word2)
gives{ 'a': 1, 'b': 2, 'c': 1 }
. -
When we compare the sets of the keys
{ 'b', 'a' }
and{ 'a', 'b', 'c' }
, we getFalse
becauseword2
contains an extra character 'c'.
Since the sets of keys don't match, we don't even need to compare the values. The function would return False
, indicating word1 and word2 are not "close".
Solution Implementation
1from collections import Counter # Import Counter from the collections module
2
3class Solution:
4 # Method to determine if two words can be made equal by swapping
5 # characters an arbitrary number of times under the condition that
6 # each character can only be swapped with the same character.
7 def closeStrings(self, word1: str, word2: str) -> bool:
8 # Calculate the frequency of each character in both words
9 frequency_word1 = Counter(word1)
10 frequency_word2 = Counter(word2)
11
12 # Get the frequency values (counts of characters) from both words and sort them
13 # Sorting is needed to compare if the words have the same frequency distribution
14 sorted_values_word1 = sorted(frequency_word1.values())
15 sorted_values_word2 = sorted(frequency_word2.values())
16
17 # Compare the sets of keys (unique characters) from both words to check if
18 # both words contain exactly the same characters
19 keys_match = set(frequency_word1.keys()) == set(frequency_word2.keys())
20
21 # Check both conditions: character counts must match when sorted and
22 # the sets of characters present in both words must be the same
23 return sorted_values_word1 == sorted_values_word2 and keys_match
24
1class Solution {
2
3 public boolean closeStrings(String word1, String word2) {
4 // Frequency arrays for each character 'a' through 'z'.
5 int[] freq1 = new int[26];
6 int[] freq2 = new int[26];
7
8 // Calculate the frequency of each character in word1.
9 for (int i = 0; i < word1.length(); ++i) {
10 freq1[word1.charAt(i) - 'a']++;
11 }
12
13 // Calculate the frequency of each character in word2.
14 for (int i = 0; i < word2.length(); ++i) {
15 freq2[word2.charAt(i) - 'a']++;
16 }
17
18 // Check if there's a character that exists in one word but not the other.
19 for (int i = 0; i < 26; ++i) {
20 if ((freq1[i] > 0 && freq2[i] == 0) || (freq2[i] > 0 && freq1[i] == 0)) {
21 return false; // Words can't be close strings if a character is not shared.
22 }
23 }
24
25 // Sort the frequency arrays to compare the frequency distribution.
26 Arrays.sort(freq1);
27 Arrays.sort(freq2);
28
29 // Compare the sorted frequency arrays.
30 for (int i = 0; i < 26; ++i) {
31 if (freq1[i] != freq2[i]) {
32 return false; // If frequencies don't match, words aren't close strings.
33 }
34 }
35
36 // If all checks pass, the words are close strings.
37 return true;
38 }
39}
40
1#include <algorithm> // Include algorithm header for std::sort
2#include <array> // Include array header for std::array
3
4class Solution {
5public:
6 // Function to determine if two strings are close.
7 // Two strings are close if you can attain one from the other using operations of
8 // swapping any two characters (often or rarely used) or transforming one character into another.
9 bool closeStrings(std::string word1, std::string word2) {
10 // We are using std::array for fixed size character frequency count
11 std::array<int, 26> charCount1 = {}; // Character frequency count for word1
12 std::array<int, 26> charCount2 = {}; // Character frequency count for word2
13
14 // Count the frequency of each character in word1
15 for (char c : word1) {
16 ++charCount1[c - 'a'];
17 }
18
19 // Count the frequency of each character in word2
20 for (char c : word2) {
21 ++charCount2[c - 'a'];
22 }
23
24 // Check the presence of characters in both words;
25 // a character must appear in both words to be close, or not at all
26 for (int i = 0; i < 26; ++i) {
27 bool charPresentWord1 = charCount1[i] > 0;
28 bool charPresentWord2 = charCount2[i] > 0;
29
30 // If a character is present in one word but not the other, they're not close
31 if ((charPresentWord1 && !charPresentWord2) || (!charPresentWord1 && charPresentWord2)) {
32 return false;
33 }
34 }
35
36 // Sort the character counts to compare the frequency of characters
37 std::sort(charCount1.begin(), charCount1.end());
38 std::sort(charCount2.begin(), charCount2.end());
39
40 // Check if both words have the same character frequency distribution
41 // If they differ at any point, the words are not close
42 for (int i = 0; i < 26; ++i) {
43 if (charCount1[i] != charCount2[i]) {
44 return false;
45 }
46 }
47
48 // If all checks pass, the words are close
49 return true;
50 }
51};
52
1function closeStrings(word1: string, word2: string): boolean {
2 // Initialize arrays to count the character frequencies in both words
3 const charCount1: number[] = new Array(26).fill(0);
4 const charCount2: number[] = new Array(26).fill(0);
5
6 // Count the frequency of each character in the first word
7 for (let char of word1) {
8 charCount1[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
9 }
10
11 // Count the frequency of each character in the second word
12 for (let char of word2) {
13 charCount2[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
14 }
15
16 // Check for the presence of characters in both words.
17 // Characters must appear in both words or not at all to be considered close.
18 for (let i = 0; i < 26; ++i) {
19 let charPresentWord1 = charCount1[i] > 0;
20 let charPresentWord2 = charCount2[i] > 0;
21
22 // If a character appears in one word but not the other, return false
23 if (charPresentWord1 !== charPresentWord2) {
24 return false;
25 }
26 }
27
28 // Sort the frequency counts of characters to compare distributions
29 charCount1.sort((a, b) => a - b);
30 charCount2.sort((a, b) => a - b);
31
32 // Compare the sorted frequency counts for both words
33 // If they differ, the words are not close
34 for (let i = 0; i < 26; ++i) {
35 if (charCount1[i] !== charCount2[i]) {
36 return false;
37 }
38 }
39
40 // If all checks pass, the words are considered close
41 return true;
42}
43
Time and Space Complexity
The given Python function closeStrings
determines if two words can be made equal by swapping the positions of the letters. This is done by checking two conditions: the sorted values of the character counters for both words are the same and the sets of characters (keys of the counters) in both words are the same.
Time Complexity:
- Creating the counters for
word1
andword2
has a time complexity ofO(N + M)
, whereN
is the length ofword1
andM
is the length ofword2
. This is because each word is traversed once to create the counts of characters. - Sorting the values of the counters has a time complexity of
O(NlogN + MlogM)
in the worst case, because the time complexity of sorting n elements isO(nlogn)
, and we are sorting the frequency counts of both words. - Comparing two sorted lists of values has a time complexity of
O(N + M)
in the worst case, assumingN
andM
are the numbers of unique characters inword1
andword2
, respectively. - Comparing two sets of keys has a time complexity of
O(N + M)
, because sets are typically implemented as hash tables, and comparing two sets involves checking that every element of one set is in the other (and vice versa), which takesO(N + M)
time in this case.
Considering the most expensive operations, the overall time complexity is O(NlogN + MlogM)
, since the logarithmic factors in sorting dominates the linear factors from other operations.
Space Complexity:
- The counters for
word1
andword2
consumeO(N + M)
space, as they store counts for the characters present in bothword1
andword2
. - Sorting the values of the counters requires
O(N + M)
space to hold the sorted lists. - The sets of keys take
O(N + M)
space as well.
Hence, the overall space complexity is O(N + M)
, which accounts for the storage of the character counts and the unique characters.
Learn more about how to find time and space complexity quickly using problem constraints.
What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.