Sponsored
Sponsored
To check whether two strings are close, you must determine if they can be made identical using the allowed operations. These operations permit swapping characters or changing all instances of one character to another, as long as they are existing characters in the particular string. Therefore, for two strings to be close:
Thus, comparing the character sets and their frequency distributions will be sufficient to determine if the strings are close.
The time complexity is O(n + m), where n and m are the lengths of the strings, due to counting characters and comparing sets. Sorting the frequencies has a time complexity of O(k log k), where k is the number of unique characters. The space complexity is O(1) since we only store counts for at most 26 characters.
1from collections import Counter
2
3def closeStrings(word1, word2):
4 if len(word1) != len(word2):
5 return False
6 counter1 = Counter(word1)
7 counter2 = Counter(word2)
8 if counter1.keys() != counter2.keys():
9 return False
10 return sorted(counter1.values()) == sorted(counter2.values())This solution first checks if the strings have the same length, as differing lengths would make it impossible for them to be close. It then uses Python's Counter to count the occurrences of each character in both strings. The first condition checks if both strings have the same set of unique characters using the keys() method, which returns a set of unique characters. The second condition checks if the frequency distributions are identical by sorting and comparing the counted values.
Alternative to directly sorting the character frequencies to compare them, we can map frequencies to counts using an intermediate structure, effectively hashing the frequency occurrences. This approach ensures that both overall character sets and their frequency distributions align.
The time complexity remains O(n + m) due to creating and comparing maps, with a space complexity of O(1) due to counting up to 26 character frequencies.
1using System;
2using System.Collections.Generic;
3using System.Linq;
4
5public class Solution {
public bool CloseStrings(string word1, string word2) {
if (word1.Length != word2.Length) return false;
var counter1 = new Dictionary<char, int>();
var counter2 = new Dictionary<char, int>();
foreach (var c in word1) {
if (!counter1.ContainsKey(c)) counter1[c] = 0;
counter1[c]++;
}
foreach (var c in word2) {
if (!counter2.ContainsKey(c)) counter2[c] = 0;
counter2[c]++;
}
var keys1 = new HashSet<char>(counter1.Keys);
var keys2 = new HashSet<char>(counter2.Keys);
if (!keys1.SetEquals(keys2)) return false;
var freq1 = new Dictionary<int, int>();
foreach (var v in counter1.Values) {
if (!freq1.ContainsKey(v)) freq1[v] = 0;
freq1[v]++;
}
var freq2 = new Dictionary<int, int>();
foreach (var v in counter2.Values) {
if (!freq2.ContainsKey(v)) freq2[v] = 0;
freq2[v]++;
}
return freq1.OrderBy(x => x.Key).SequenceEqual(freq2.OrderBy(x => x.Key));
}
}The C# solution follows a similar structure as the Java code, using Dictionary for character counts and frequency counting. The final comparison checks equivalence through sorted lists of frequency mappings, validating matching distributions.