Solving Popular Algorithms: Replace “?”s

Welcome back to another week of Hope explaining her problem solving strategy to the void. Today, we are going to be looking at another LeetCode problem called Replace All “?”s to Avoid Consecutive Repeating Characters. I actually really enjoyed the process of solving this problem and think some of the methods I used to solve it are generally quite helpful problem solving practices. So let’s jump right in!

Cute doggy + ?s

The Problem

The goal of this problem is, given a string of characters, to replace any ? in the string with a character that is different from the previous and/or next character in the string.

For example, if our given string is “?zs”, then an acceptable solution would be “azs” or “bzs” or “czs” or “basically any other letter in the alphabet other than z zs”.

Similarly, if our given string is “ubv?w”, then an acceptable answer could be “ubvhw” or again “ubv any character that isn’t v or w w”.

Now that we understand the goal of our problem, let’s move onto our solution.

The Solution: An Overview

One thing I find super helpful when attempting to solve algorithm problems, is taking the time to brainstorm and write out my problem solving steps. AS tempting as it can be to jump right into writing code, often spending time to make a map of your solution can save you a lot of coding time later on.

For the solution, as an example, I knew that I would probably need some sort of loop in order to find all of the ?s in the string. I also knew that in that loop, I would probably want to have two trackers, one for any character before a ? and one for any character after a ?.

Then, once the ?s are found, I knew that I would need some way to find a new character that was neither the previous or following character to the ?.

Finally, I thought that I could probably use the JS method splice in order to remove the ? and replace it with my new character.

With those basic steps in mind, I knew that the next step in my problem solving, perhaps the most difficult step, would be figuring out how to get the new character to replace each ? in my string.

The Solution: getRandomChar

After playing around with a few different ideas, I realized that simplest way to get a new character to insert into my string was to make a separate function that I called getRandomChar.

One thing I found tend to forget about when writing algorithms is that sometimes it can be super helpful to write an extra function to complete a task that you might need to run multiple times in your algorithm. This practice is not only helpful for algorithms, but also in general helps keep your code DRY and much easier to read.

Now, the goal of this function is basically just what it sounds like: to find a random alphabetical character that we can then insert into our string. To make this function work for the purpose of our problem, however, I passed in two arguments, “prev” and “nxt”. We will get the value of these two arguments when we call our getRandomChar function.

let getRandomChar = (prev, nxt) => {
    let alphaArr =   ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i',        'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
    
    let randomChar = alphaArr[Math.floor(Math.random() *   alphaArr.length)]
    while (randomChar === prev || randomChar === nxt) {
        randomChar = alphaArr[Math.floor(Math.random() * alphaArr.length)]
    }
    
    return randomChar
}

As you can see, this function works pretty simply. First, we declare an array containing every letter in the English alphabet, alphaArr. Then, we declare another variable, randomChar, whose value is just one random character from our alphaArr. Then, and this is probably the most important part, we check to make sure that randomChar does not equal either of our two arguments, prev or nxt, and if it does we find a new random character from our array.

Now, I used a while loop here, instead of, say, an if/else statement, because we need to find a random character that does not equal either prev or nxt. If we were to use an if/else statement, we could basically check once to see if the values were equal. Using a while loop, however, our loop will run while randomChar equals either prev or nxt.

Finally, our function will return our random character that does not equal either prev or next.

With that out of the way, we can move onto solving the rest of our problem.

The Solution: Putting it all together

I already briefly walked through the overview to our solution above, but just to recap we will be writing a loop that will check to see if any value in our string is a ?. When we find a ?, we will use two trackers, prev and nxt, to keep track of the characters that come before and after our ?. Then, we will call on our getRandomChar function, passing in our tracker variables as arguments, to find a new character that we can then splice into our string and replace our ?.

With all that in mind, there is just one thing to consider before we write out our solution in code: splice does not work on strings.

To solve this issue, I just used to the JS method split in our to split our string into an array, which splice will work on. However, this is definitely not the only solution to this issue so feel free to figure out another way to solve this problem without converting our original string into an array!

Now that we have an idea on how to solve this problem, here is the final code for our solution:

var modifyString = function(s) {
    
    let splitS = s.split("")
    
    for (let i = 0; i < splitS.length; i++) {
        if (splitS[i] === '?' && i > 0) {
            let prev = splitS[i-1]
            let nxt = splitS[i+1]
            let newChar = getRandomChar(prev, nxt) 
            splitS.splice(i, 1, newChar)                      
        } else if (splitS[i] === '?') {
            let nxt = splitS[i+1]
            let newChar = getRandomChar("1", nxt)
            splitS.splice(i, 1, newChar) 
        } else if (splitS[i] === '?' && !splitS[i+1]) {
            let prev = splitS[i-1]
            let newChar = getRandomChar(prev, "1")
            splitS.splice(i, 1, newChar)
        }
    }
    
    return splitS.join("")
    
};

You may notice the chunky if/else if/else statement I have in this solution and this is to account for the times when the ? is either in the first or last position in our string. When a ? is the first position, there will be no previous value and thus when we call our getRandomChat function, which requires two arguments, we can pass the value “1” instead of a prev value. Similarly, when ? is in the last position, there will be no next value and thus again we can pass into “1” instead of nxt when we call our getRandomChar function.

Finally, once we have successfully replaced every ? with an appropriate character, we can return our string (but don’t forget to join the string so it’s no longer an array!) and our problem has been solved!

I hope you enjoyed the guide to my solution to this problem. I want to note that every time I practice solving problems I get faster and faster and each solution comes easier. Just yesterday, I, for the first time, solved a problem in one go! So, if you are new to algorithms and/or are studying for a technical interview, make sure to practice problems like this one on your own!

As always, good luck and happy coding!

Cute doggy 2 + ?s