https://leetcode.com/problems/determine-if-two-strings-are-close/
Language: Python — Time: 10 minutes
Full Code on Gitfront.io — https://github.com/cswartzell

This was hands down one of my favorite problems so far. Ill list it in full here:

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.

The reason I loved this is… its a trick. Rather than a wrote exercise in coding existing patterns, or a brain bender of a challenge requiring arcane wizardry, this problem just asks you to think.

The first clue is in the description of the first operation. If you can swap any two letters in a word, and you can perform that operation any number of times then you can create whatever arrangement you want from the word. The mechanics of the operation are meaningless: the letters can be arranged however you’d like. We will never need to perform a swap operation on one of the words to “test” its ability to become the other. If we can ensure the two words have the right number of letters, we can ignore their arrangement and this rule.

But how do we know if we have the right letters? Well first we note we can only swap between existing letters. 5 letter “A”s can swap with 3 letter “B”s such that we have 3 “A”s and 5 “B”s. That means if one word has a letter the other doesnt then we can terminate as False. We cannot generate a missing letter nor lose an existing letter. We merely need to make a hashset out of each word and ensure the two words contain exactly the same letters.

But how many of each letter? Back to the example of our 5 “A”s and 3 “B”s, we see after swapping them we still have 5 of one letter and 3 of another. We can never affect the total count of the various letter groupings, merely what letter happens to be assigned to them. We have thus far determined that our two words have the same sets of letters. If the two words have the same grouping sizes (say, 5 of letter #1, 3 of letter #2, and 1 of letter #3), then we can swap the labels on these groups such that the two word sets will have the same frequencies per letter. This catches the trivial case that the words need to be of equal length.

We can use a basic hashmap to simply check these two conditions. The Python Counter() collection can be used to automatically create an unordered hash with the letters of our strings as the keys, and their frequency within a word as the values. We then check the lists of keys for both words are the same (affirming the two words have the same and only the same letters), and then compare their values lists (affirming they have similar “letter frequency groups”, regardless of what letter is attached to them).

We don’t need to perform any swaps. We don’t need to implement either operation. We don’t simulate the transformation of one word to the other. Using just logic we can extend the existing rules to think about what they ultimately mean, and reduce the problem to a much simpler one. Rather than math trickery or hacky shenanigans (which, to be fair, I also love) this can be solved in just a few lines with basic reasoning:

I love it.