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)
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.
Implementations
Python
from collections import Counter
class Solution:
def closeStrings(self, word1: str, word2: str) -> bool:
if len(word1) != len(word2):
return False
sw1 = set(word1)
sw2 = set(word2)
if sw1 != sw2:
return False
cw1 = Counter(word1)
cw2 = Counter(word2)
if sorted(cw1.values()) != sorted(cw2.values()):
return False
return True
Imagine you have two bags of LEGO bricks, word1 and word2. We want to see if these bags are "close" to being the same, even if the bricks are arranged differently.
Are they the same size?
🐍if len(word1) != len(word2): return False
🐍First, we check if the bags have the same number of LEGO bricks. If they don’t, they can’t be “close,” so we say “no.”
Do they have the same kinds of LEGOs?
🐍sw1 = set(word1)
🐍sw2 = set(word2)
🐍if sw1 != sw2: return False
🐍Next, we look at what kinds of LEGO bricks are in each bag. set() helps us find the unique kinds. If one bag has red bricks and the other has blue, they're not "close," even if they have the same number of bricks.
How many of each kind?
🐍cw1 = Counter(word1)
🐍cw2 = Counter(word2)
🐍Now, we count how many of each kind of LEGO brick are in each bag. Counter() does this for us. It's like making a list: "3 red bricks, 2 blue bricks..."
Do they have the same counts?
🐍if sorted(cw1.values()) != sorted(cw2.values()): return False
🐍We take the counts (3, 2, etc.) and put them in order from smallest to biggest. If the ordered counts are different, the bags aren’t “close.” For example, one bag might have “2 red, 3 blue,” and the other might have “3 red, 2 blue.” Even though the bricks are different, the amounts are the same when sorted.
🐍This is like saying if both bags when put in order have the same amount of each number of brick types, then they are close.
They’re close!
🐍return True
🐍If we get through all those checks, it means the bags are “close.” They have the same kinds of LEGO bricks, and the same amounts of each kind, even if they’re arranged differently.
Typescript
function closeStrings(word1: string, word2: string): boolean {
if (word1.length !== word2.length) {
return false;
}
const count1: { [key: string]: number } = {};
const count2: { [key: string]: number } = {};
for (const char of word1) {
count1[char] = (count1[char] || 0) + 1;
}
for (const char of word2) {
count2[char] = (count2[char] || 0) + 1;
}
if (Object.keys(count1).sort().join('') !== Object.keys(count2).sort().join('')) {
return false;
}
const freq1 = Object.values(count1).sort((a, b) => a - b);
const freq2 = Object.values(count2).sort((a, b) => a - b);
return freq1.join('') === freq2.join('');
}
Imagine you have two bags of LEGO bricks, and each brick has a letter on it. We want to know if the bags are “close” to being the same.
Are the Bags the Same Size?
🧱First, we check if the bags have the same number of LEGO bricks. If they don’t, they can’t be “close,” so we say “no” (return false).
Counting the Bricks in Each Bag
🧱We count how many of each letter we have in each bag.
🧱For example, if bag 1 has “aab,” we know we have two “a”s and one “b.” We do the same for bag 2.
Do They Have the Same Letters?
🧱We check if both bags have the same kinds of letters.
🧱We put all the letters from each bag in alphabetical order and see if they match.
🧱For example if bag one has “a”,”b”,”c” and bag two has “c”,”a”,”b” then when sorted both will be “abc”.
🧱If the letters are different, we say “no” (return false).
Counting the Amounts
🧱We take the counts of each letter from each bag and put them in order from smallest to biggest.
🧱For example, if bag 1 had “aab,” the counts would be 2 “a”s and 1 “b.” So, we’d have the numbers 1 and 2.
🧱We do the same for bag 2.
Do They Have the Same Amounts?
🧱We compare the ordered counts from both bags. If they’re exactly the same, it means the bags are “close,” and we say “yes” (return true).
🧱If the counts are different, we say “no” (return false).
Go
import "sort"
func sameKeys(m1, m2 map[rune]int) bool {
if len(m1) != len(m2) {
return false
}
for key := range m1 {
if _, ok := m2[key]; !ok {
return false
}
}
return true
}
func closeStrings(word1 string, word2 string) bool {
if len(word1) != len(word2) {
return false
}
freq1 := make(map[rune]int)
freq2 := make(map[rune]int)
for _, char := range word1 {
freq1[char]++
}
for _, char := range word2 {
freq2[char]++
}
if !sameKeys(freq1, freq2) {
return false
}
freqVals1 := make([]int, 0, len(freq1))
freqVals2 := make([]int, 0, len(freq2))
for _, val := range freq1 {
freqVals1 = append(freqVals1, val)
}
for _, val := range freq2 {
freqVals2 = append(freqVals2, val)
}
sort.Ints(freqVals1)
sort.Ints(freqVals2)
for i := 0; i < len(freqVals1); i++ {
if freqVals1[i] != freqVals2[i] {
return false
}
}
return true
}
Starting here:
sameKeys(m1, m2 map[rune]int) bool
🐻Think of this like checking if two toy boxes have the same kinds of toys, even if they have different numbers of each toy.
🐻m1and m2 are like the toy boxes. Each toy (letter) has a number (how many of that letter there are).
🐻This part makes sure both boxes have the exact same toys (letters). If one box has a toy the other doesn’t, they’re not the same.
Then:
closeStrings(word1 string, word2 string) bool
🐻This is where the main “close strings” game is played.
Are they the same length?
🐻First, we check if the words are the same length. If they aren’t, they can’t be close. It’s like trying to fit a long snake into a short box — it won’t work.
Counting the letters
🐻We make two more toy boxes, freq1 and freq2.
🐻We go through each word and put each letter in its box, adding a counter to show how many times we see it.
🐻For example if word1 is “abbccc”, then freq1 will have ‘a’:1, ‘b’:2, ‘c’:3
Do they have the same toys?
🐻We use our sameKeys function to check if the two toy boxes have the same kinds of letters. If they don't, the words aren't close.
Counting how many of each toy
🐻We make two lists called freqVals1 and freqVals2.
🐻We take the numbers from our toy boxes (how many of each letter we had) and put them in these lists.
🐻For example, if freq1 had ‘a’:1, ‘b’:2, ‘c’:3, then freqVals1 will be [1,2,3]
Putting the numbers in order
🐻We put the numbers in each list in order from smallest to biggest (like lining up toys by size).
🐻So [3,1,2] would become [1,2,3]
Are the numbers the same?
🐻Finally, we go through the lists of numbers. If all the numbers in the first list match the numbers in the second list, in the same order, then the words are close!
If you liked this article I’d appreciate an upvote or a comment. That helps me improve the quality of my posts as well as getting to know more about you, my dear reader.
Muchas gracias!
Follow me for more content like this.
X | PeakD | Rumble | YouTube | Linked In | GitHub | PayPal.me | Medium
Down below you can find other ways to tip my work.
BankTransfer: "710969000019398639", // CLABE
BAT: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875",
ETH: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875",
BTC: "33xxUWU5kjcPk1Kr9ucn9tQXd2DbQ1b9tE",
ADA: "addr1q9l3y73e82hhwfr49eu0fkjw34w9s406wnln7rk9m4ky5fag8akgnwf3y4r2uzqf00rw0pvsucql0pqkzag5n450facq8vwr5e",
DOT: "1rRDzfMLPi88RixTeVc2beA5h2Q3z1K1Uk3kqqyej7nWPNf",
DOGE: "DRph8GEwGccvBWCe4wEQsWsTvQvsEH4QKH",
DAI: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875"