Leetcode 1221. Split a String in Balanced Strings

Problem Explanation

Given a string s containing only 'L' and 'R' characters, we are to split the string into as many substrings as possible such that each substring contains an equal amount of 'L' and 'R' characters.

For example, given the string s = "RLRRLLRLRL", we can split it into 4 substrings with equal 'L' and 'R' as follows: "RL", "RRLL", "RL", "RL".

The approach to solve this problem is to iterate through the string and keep count of 'L' and 'R'. If the count of 'L' and 'R' is equal at any point while iterating through the string, we have found a balanced substring and increment our result counter.

Solution

Python

1
2python
3class Solution:
4    def balancedStringSplit(self, s: str) -> int:
5        # Initialize variables
6        res, count = 0, 0
7        
8        # Iterate over the string
9        for c in s:
10            count += 1 if c == 'L' else -1
11            
12            # If the count is 0, a balanced string has been found
13            if count == 0:
14                res += 1
15                
16        return res

Java

1
2java
3class Solution {
4    public int balancedStringSplit(String s) {
5        int res = 0, count = 0;
6        
7        // Iterate over the string
8        for(char c : s.toCharArray()){
9            count += c == 'L' ? 1 : -1;
10            
11            // If the count is 0, a balanced string has been found
12            if(count == 0){
13                res++;
14            }
15        }
16        
17        return res;
18    }
19}

JavaScript

1
2javascript
3var balancedStringSplit = function(s) {
4    let res = 0, count = 0;
5        
6    // Iterate over the string
7    for(let c of s){
8        count += (c === 'L') ? 1 : -1;
9            
10        // If the count is 0, a balanced string has been found
11        if(count === 0){
12            res++;
13        }
14    }
15        
16    return res;
17};

C++

1
2c++
3class Solution {
4public:
5    int balancedStringSplit(string s) {
6        int res = 0, count = 0;
7        
8        // Iterate over the string
9        for(char c : s){
10            count += c == 'L' ? 1 : -1;
11            
12            // If the count is 0, a balanced string has been found
13            if(count == 0){
14                res++;
15            }
16        }
17        
18        return res;
19    }
20};

C#

1
2csharp
3public class Solution {
4    public int BalancedStringSplit(string s) {
5        int res = 0, count = 0;
6        
7        // Iterate over the string
8        foreach(char c in s){
9            count += c == 'L' ? 1 : -1;
10            
11            // If the count is 0, a balanced string has been found
12            if(count == 0){
13                res++;
14            }
15        }
16        
17        return res;
18    }
19}

In all the above solutions, we maintain a counter that gets incremented when we encounter a 'L' and decremented when we encounter a 'R'. The counter is initialised to 0. When the counter becomes zero again it means that we have seen the same number of 'L' and 'R' characters which forms a balanced string, so we count it. The process is repeated for the entire string to find all the balanced strings.This problem could be seen as a question of string parsing, where the target is to identify and count the substrings that contain an equal number of 'L' and 'R' characters. The given solutions in Python, Java, JavaScript, C++ and C# all take advantage of a counter to track the balance between appearing 'L's and 'R's, and increment a separate counter indicating the number of identified balanced strings each time a balance is reached.

This approach is very efficient, as it allows the problem to be solved in a single pass through the string, resulting in a time complexity of O(n), where n is the length of the string.

However, it should be noted that this solution assumes that the input string only contains 'L' and 'R' characters, and is strictly alternating between those two characters. It would fail in case the string includes other characters or multiple copies of 'L' or 'R' appear consecutively.

For dealing with other characters, an error checking procedure should be added prior to the main logic of the solution, to quickly go through the string and validate that it only contains 'L' and 'R' characters.

As for the case when multiple 'L' or 'R' appear consecutively, the simplest way to handle it would be to modify the counter updating logic. Instead of incrementing or decrementing the counter by one, a loop should be added to keep updating the counter until a different character is encountered. This would mean that the string is parsed character by character but each character is also checked against the next character, causing a slight increase in time complexity. However, overall, this approach would still maintain a linear relationship with the size of the string, thus preserving a time complexity of O(n).

These are some potential modifications to make the solution more robust and adaptable to different variations of the problem. While they may not be necessary for the original problem as stated, they are worth considering when applying the solution to real-world tasks.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫