As I continue in my job hunt, I’m working on continually expanding and honing my skill set, while also working on interview prep work. One part of the process that I’ve been spending a solid amount of time on is practicing algorithm problems. I weirdly enjoy these practice problems quite a bit; it feels to me a bit like a game, or a puzzle, that I get to solve and they’re usually nicely self-contained. Of course, there are those moments when you feel absolutely stuck and have no idea how to solve the puzzle laid out in front of you and you feel like pulling your hair out. Here is one just problem that totally stumped me, and I felt it might be useful for others to see it for themselves, as well as a possible solution. This particular solution was the only one I could come up with, so it is in no way optimized for speed and efficacy, so if anyone has a cleaner/faster solution, I’d love to see it.
The Problem
This particular practice problem is from binarysearch.io, and I very much enjoy using them, but there are several excellent sites for practice problems, such as leetcode.com.
The explanation for the output of 2 in the above example is because we can take the substring “ooba” out of string s, change the “b” and “a” into “p” and “s”, which would match the substring with the string t. So, let's walk through this:
Since the instructions ask us to return an integer of the minimum number of characters we need to change in string t to match string s, we know we need a variable that keeps track of that minimum value. So let's set a variable and call it min, and initialize it to the value of t.length, since we can expect, at worse, for the minimum number of characters needed to be changed is all of them.
Now we know we need to check each element in t against every element in s, and we know we a for loop can help us accomplish this.
We are only checking t against s as many times as there are “open” spaces for t to move down the chain, i.e. the difference in the length of the two strings, so we’ll use that as the conditional for our for loop. This loop we will use to check each element in s, but we’ll need a second, nested-loop to check each element of t against that single s element before moving on. We’ll also need a counter to increment based on how many times we would change an element to match string t. Inside this second nested loop, we’ll write our logic so that every element in s in the first loop will get checked incrementally against every element in t during the second loop. That looks something like this:
Where I was getting stuck, I didn’t initially have the variable j=i set. This is paramount because we need to move down the length of s during each iteration of our nested loop, whereas the top loop is responsible for shifting where the starting point of the check against s is over the course of the loop.
After we finish an iteration of our nested loop, we incriminate the counter for the number of elements in the substring needed to be changed to match string t, which we will need to then check against our existing min variable. Once that is done, we have our solution!
I hope this proved to be helpful as you work on your own practice problems, and please let me know if you find a faster solution.
