Problem
Given two strings word1 and word2, returntrue if word1 and word2 are close. Otherwise, return false.
Two strings are considered close if one can be transformed into the other using these operations: swapping any two existing characters, or transforming every occurrence of one existing character into another existing character and vice versa.
Both strings must therefore contain the same set of distinct characters, and the frequencies of those characters must be the same as a collection, even if the frequencies are assigned to different characters.
Example(s)
Consider the following examples to understand the expected input and output.Example 1
Input
word1 = "abc"
word2 = "bca"Output
trueExample 2
Input
word1 = "a"
word2 = "aa"Output
falseSolution
This solution uses HashMap and HashSet concepts to compare the character sets and their frequencies. We first count the frequency of every character in both strings.For the strings to be close, they must have the same distinct characters. Their frequency distributions must also be identical, regardless of which character has which frequency. Therefore, we sort the frequency arrays and compare them.
class Solution {
public boolean closeStrings(String word1, String word2) {
if (word1.length() != word2.length()) {
return false;
}
int[] freq1 = new int[26];
int[] freq2 = new int[26];
for (char c : word1.toCharArray()) {
freq1[c - 'a']++;
}
for (char c : word2.toCharArray()) {
freq2[c - 'a']++;
}
for (int i = 0; i < 26; i++) {
if ((freq1[i] == 0) != (freq2[i] == 0)) {
return false;
}
}
Arrays.sort(freq1);
Arrays.sort(freq2);
return Arrays.equals(freq1, freq2);
}
}Complexity
Counting the character frequencies takesO(n) time. Since the frequency arrays contain only 26 elements, sorting them takes constant time. Therefore, the overall time complexity is O(n), where n is the length of the strings.
The solution uses two fixed-size arrays of
26 elements, so the extra space complexity is O(1).