Solving Popular Algorithms: Balancing Strings

Welcome back to yet another week of solving popular algorithms. Once again we will be looking at a leetcode problem. Today’s is a pretty fun one called Split a String in Balanced Strings.

Without further ado, let’s jump right into solving this problem!

A kitty trying to find balance

The Problem

You are probably wondering what a balanced string is and that is an excellent question. For the purpose of this problem, a balanced string will be considered a string that has an equal number of ‘L’ and ‘R’ characters. For example, a string that looked like ‘RLRL’ would be considered to be balanced.

Now that we understand what a balanced string is, let’s discuss the actual goal of this problem, which is, given a balanced string, s, split it into the maximum amount of balanced strings and return the maximum amount.

Let’s look at an example:

s = "RLRRLLRLRL"

Looking at this string, we can determine that within it there are four substrings that could be considered balanced. First, we have “RL”. Then, the next balanced substring would be “RRLL”. Then, finally, we could get in two more balanced substrings, both made up of “RL”. As a result the answer we would want our function to return would be 4.

Hopefully, you now understand the goal of this problem and we can move onto solving it.

The Solution: An Overview

To solve this problem, our main goal is really keeping track of whether or not a string is balanced. One thing you might be tempted to do is some crazy nested looping to keep track of each character in the string. Or maybe that was just me…

However, I can assure you that we don’t need to do that. Instead, we can keep track of the balance in string using a variable I very helpfully named “balance”. Then as we loop through the string, we can increment our balance variable when we come across an “R” and decrement our balance variable when we come across an “L”. Then, if that balance variable ever returns to 0, we know that we will have come across an equal number of Ls and Rs and as a result we have found a balanced substring within our string.

If you’re feeling a little lost by this concept, don’t worry we will go over it in greater detail below!

The Solution: The Code

balancedStringSplit = (s) => {
  let balance = 0
  let answer = 0
  for (let char of s) {
  
    if (char === "R") {
      balance++
    } else {
      balance--
    }
    if (balance === 0) {
        answer++
    }
  }
  return answer
};

Like we discussed above, the strategy to solving this problem is using a variable to keep track of whether or not our substring is balanced. By incrementing when we reach an “R” and decrementing when we reach an “L”, we can determine that a substring is balanced when our balance variable returns to 0.

Finally, once balance is at 0, we know we have found a balanced substring and as a result we can increment our answer variable. Then, once we have looped through our entire string, we can return answer, which will have been properly incremented for each balanced substring we came across in our original string.

Now, I know that this has been a pretty quick and dirty explanation of this solution. However, I also know that this was a solution I was only able to come up with because I had seen similar problems solved in a similar way. One thing that I think would be great to note about solving algorithms is that often you can recycle problem solving strategies. While practice is obviously vital, sometimes the easiest way to solve a future problem is by seeing a solution for a similar problem. Ultimately, everything you learn about solving algorithms will help you solve future ones you might come across!

As always, good luck and happy coding!

A monkey with perfect balance