Are you, really, a problem solver!
Being a software engineer is another way of saying that you are a problem solver, maybe the opposite isn’t correct but, let’s not argue about that here. We, software engineers, are always developing our problem-solving skills along the way of our career. But, many may be solving problems just by applying techniques and algorithms to solve them, then it becomes more of a selection process from a pool of algorithms and techniques that you already have. This is not wrong, but this is not all about solving a problem. Solving a problem requires a much more diverse skillset, algorithm selection is one of them but, what about the others? To help identify what kind of a skillset, let me ask those questions. How much time do you stick to your thought process before giving up and switch to another approach? How fast do you narrow down your solution space? Do you found yourself more often being biased to an approach just because you thought it’s similar to a problem you solved before but then, you found that you are drifted away from reaching the correct solution? Did you ever solve a problem but then you realized that it’s much simpler than you thought? Have you ever asked yourself those kinda questions? If no, then this is a big red flag 🚩of weakness in your problem-solving skillset.
In this article, we will go through an exercise, the whole thought process, to solve a given problem and see how would it be to develop your problem-solving skillset, not just solving the problem. We will, together, highlight some of those important skills that you should focus on developing. Let’s start.
It is a LeetCode problem called Determine if Two Strings Are Close where we are given two strings to determine if we can transform any of the two strings to be exactly as the other one using only 2 operations, a swap and a transform operation. That is, return true if any of the strings can be transformed to the other one, and false otherwise. The swap operation allows you to swap any two existing characters in a string:
ex: str = "aaxbzcc"
str.swap(x,z) ==> "aazbxcc"The transform operation allows you to transform all occurrences of a character in a string into another existing character in the string and do the same for the other character
Ex: str = "aaxcc"
str.transform(a,c) ==> "ccxaa"Here we transform all occurrences of the letter “a” into “c” and all occurrences of “c” into “a”. Now that we understand the problem, let’s solve it.
As mentioned before, I will go through my thought process just to point out what mistakes I did that we all can learn from it and see how can we develop those weaknesses. The first thing I thought of when first reading the description is that it’s an edit distance problem, but maybe a simplified one. I picked up a paper and a pencil and tried to solve this as if I am a machine where I look at a character at a time and see if the corresponding character in the other string is the same. If they are equal, I continue, if not, I will branch into two different paths, a path that starts manipulating the string using the swap operation and the other path by applying the transformation.
First Approach1. If <string1> == <string2> return true.
2. Else, check <string1>[i] against <string2>[i], if equal, check the next.
3. Else, do 2 recursive call, one after applying the swap operation on <string1>, and the other after applying the transform operation on <string1>.
The idea for me was that I will try all possible ways to apply the 2 operations recursively until I can make both strings equal, again, this is how the edit distance algorithm works.
I used this test case, “abc” as the first string and “bca” for the second. Just to be on the same page, I will assume that we will always want to transform the first string to the second one and anywhere I say the current character I mean the character that I’m checking in the first string and the desired character is the character corresponds to the current character by position in the second string, for example, in the previous test case that I have chosen, if the current character in the first string is “a” then the desired character is “b” from the second string.
So, I compared the first character of both strings which are, obviously, different letters. Now, I should have 2 paths, one per operation being applied on the first string. One issue that I found is how I’m gonna apply either the swap or the transform operations on a string? What criteria? honestly, I had no idea 😂 and I just make out those rules.
swap(<current>, <desired>): Search for the first occurrence of the desired character in the first string and swap it with the current one, if no occurrences then this path is wrong and I should return.transform(<current>, <desired>): simply transform the current character into the desired character.
Let’s put those 2 rules into action. In the example we choose, the current character is “a” and the desired one is “b”, different characters, let’s do a swap, applying the swap rule, the first occurrence of the desired character in the first string is at position 2, assuming 1-based indexing. Let’s swap it, now we have transformed the first string into this one “bac” by applying the swap operation.
Cool, let’s stick with that path following the depth-first behavior of any recursive algorithm. Moving on, the current character now is the “a” from the first string and the desired character is “c” from the second one. Yes, they are different, again we have 2 operations that we can apply, hence two different paths, let’s stick with the swap path. The first occurrence of the desired character “c” in the first string is at position 3. Great, let’s swap it. Guess what, the first string is now “bca” which is the same as the second one, cool 🎉 we did it. Now we can return true.
This was easy, although we only tried the algorithm on a simple example. At that point, I had no clue if the algorithm is correct. I just made out those rules and applied them on a simple example and it worked. So, I tried another one, this time the first string is “cabbba” and the other is “abbccc”.
So, the current character is “c” and the desired one is “a”, they are different, then we should do a swap in one path and a transform in another. The swap path will transform the string to this one “acbbba”. Let’s continue on this path for a while. Now the current character is “c” and the desired one is “b”, they are different. Again, 2 operations can be applied, the swap will transform it to be “abcbba”. Up till now, we are at the third character and the first 2 characters of both strings are identical, we are doing great🎉.
Next, the current is “c” and the desired is “b”, do a swap, now we have this string “abbcba”. For the sake of explanation, let’s try the other path this time, where the first string was at this state “abcbba” and after applying the swap on the third character it became “abbcba”. For the transform operation, transform all occurrences of “c” into “b” in the first string and vice versa. So, “abcbba” will transform into “acbcca”. Did you notice that after applying the transform we mess up the first 2 characters? If we continue on this example we will always reach a close state and then a transform operation will mess up everything😕.
Even though I noticed this while solving this example myself, I continued on until I reach the final recursive call! Don’t worry, I will not do the same here 😂. So, this algorithm is totally wrong. Why? because of the transform operation, it will always work on parts that we already fixed before. In the edit distance algorithm, it doesn’t mess up any previous state. And it’s the case for any divide-and-conquer algorithm, the algorithm should only be concerned with the current sub-problem without knowing anything about other parts of the problem, which is not the case here.
Sadly, I decided to search for another approach, but this time, I will ask for help. On LeetCode, they have monthly challenges to solve a problem each day. This problem was one of the January LeetCoding Challenge and they provide hints you can use if you stuck solving a problem which is the case for me at that point. This problem had 2 hints, the first is:
Operation 1 allows you to freely reorder the string.Yes, it makes sense as it’s a swap operation 😅. For the other hint, I thought it will be something like “Operation 2 allows you to freely transform the strings’ characters 😂” but luckily it wasn’t, the other hint is:
Operation 2 allows you to freely reassign the letters’ frequencies.What? frequencies? but I don’t have any frequencies in either the problem definition or in my first approach! And, as always, toilet is where ideas shine 💡. It took me like 5 minutes to completely threw off my first approach, and then I said, what if I reordered the first string characters so that we have equal character frequencies correspondence. For example, if I had “cabbba” and “abbccc” I can reorder the first string to be “caabbb”, this is showing how precise the first hint is, the reordering part.
All this came to my mind while in the toilet. But, both strings still not identical, we have to transform the characters! So, the first character of the reordered string is “c” and the desired one in the second string is “a”, then we transform “c” into “a” in the reordered string to be “accbbb”. Note, we transform in both ways, all occurrences of “c” transforms to “a” and vice versa. The next one “c” and the desired is “b”, so we transform “c” into “b” to have this “abbccc”.
Wow, we are done, and we only used the first hint. But what about the second one, the frequencies? Ah, I got this, if you noticed that after reordering the first string, both strings now are having equal character frequencies correspondence. In the reordered string, we have one “c” corresponds to one “a” in the second string, then 2 “a” corresponds to 2 “b”, and finally, 3 “b” corresponds to 3 “c”. This blows my mind🎇. I found that I don’t have to actually mutate the strings to transform one into the other, I just have to check if we have matching frequencies! I immediately started writing code.
Second Approach:1. Loop through each string to count charachter frequencies.
2. Check if there is frequency correspondence between the strings
3. If yes, return true, and False otherwise
After finishing my first version of implementing this algorithm, I tried some test cases before submitting the code, and when I submit it, I had a wrong answer😣. This one, “uau” and “ssx”, my algorithm returns true while the LeetCode is returning false. But why? According to the second approach, I have frequency correspondence between both strings
"uau": 'u' => 2, 'a' => 1
"ssx": 's' => 2, 'x' => 1It took me like half an hour, and after reading the problem definition again, I found this,
Transform Operation: Transform every occurrence of one existing character into another existing characterThen I realized that in order to transform(<char1>, <char2>), both char1 and char2 should exist in the string. That is, the characters in the first string, “uau”, are totally different from the second one “ssx”. I reflected this in the code so that the unique set of characters in both strings should be identical. Meaning that the unique character set of the string “uau” is the set {‘u’, ‘a’} and for the “ssx” string, it’s {‘s’, ‘x’}. So, both sets are not equal. On the contrary, in our first example “abc” and “bca”, both have identical unique character set which is the set {‘a’, ‘b’, ‘c’}. I resubmit and I got accepted! 🎉
Refine The Second Approach:1. Loop through each string to count character frequencies.
2. Check if there is frequency correspondence between the strings.
3. Check if both strings have the same character set.
4. If both checks pass, return true, and False otherwise.
The moral of the story is when you stuck, just go to the toilet😛. Of course, this will not solve all of your problems, but sometimes it can help 😂. Let’s revisit the questions I mentioned at the beginning of this story and see how we can apply them to this problem. Obviously, the first mistake I have done is being biased towards an algorithm or a technique, which is what I did when I assumed that this is a simplified version of the edit distance algorithm. This is a skill that you should develop which is how you correctly decide whether this algorithm a good fit or not. And when not, you should immediately throw it away. This leads us to the second mistake I had done, how much time did I stick to my approach? As I mentioned, I already knew that my first approach was not correct while solving the example however, I continued solving it. This waste my time, you should know when to switch to another approach. Also, combining this skill with the algorithm selection skill so that you can try as many as you can in a short time will make you a dangerous problem solver but, it’s not easy to master, it takes much time.
As we saw earlier, my first approach was not making any sense however, don’t prevent yourself from trying dump solutions, really, this is so helpful, and it develops your mental activity for searching your solution space. Next time you will start off with a smart approach, maybe next you will have the correct algorithm from the first shot. And even further, at some point, when you are really dangerous at solving problems, you may come up with a fully optimized solution from the first time, but this is really, really, hard. The next skill that you should master is, defining the scope of your solution. For example, we did not have to actually transform the string, we just do some checks, we make sure that both strings have equal character frequency correspondence, and both strings should have the same unique character set. Last but not least, please, read the problem definition carefully. Avoid getting wrong submissions just like me.
As we know, you cannot teach a kid riding a bike just by watching you riding one. The same is here, you need to try solving the problem on your own, don’t look at how others solve it. Unleash the real potential and creativity of your mind. Believe me, you will find a masterpiece inside your head.
I think this is it, we have gone through a real thought process and discussed mistakes to avoid and skills that we should master to really become a problem solver. And for writing the code for this problem, this can be an article on its own, so I decided to write another story for this, of course, if you like this type of thought process stories.
