Split a String in Balanced Strings

Problem Link: Split a String in Balanced Strings

Problem #

Balanced strings are those that have an equal quantity of ‘L’ and ‘R’ characters.

Given a balanced string s, split it into some number of substrings such that:

Each substring is balanced. Return the maximum number of balanced strings you can obtain.

Example 1:

Input: s = “RLRRLLRLRL”
Output: 4
Explanation: s can be split into “RL”, “RRLL”, “RL”, “RL”, each substring contains same number of ‘L’ and ‘R’.

Thoughts #

Given the input string is balanced, actually we are finding how many positions we can split the string to make sure each substring is balanced. It’s easy to think of we can use gready method to solve this problem. As long as we find a balanced substring, we can split it and start to find the next one.

class Solution:
    def balancedStringSplit(self, s: str) -> int:
        cnt=1 if s[0]=='L' else -1
        ans=0
        for i in s[1:]:
            if i=='L':
                cnt+=1
            else:
                cnt-=1
            if cnt==0:
                ans+=1
        return ans 

Explanation #

1. We use a counter to count the number of ‘L’ and ‘R’ characters
2. We initialize the counter to 1 if the first character is ‘L’ and -1 if it’s ‘R’
3. We iterate through the string starting from the second character, updating the counter based on whether we encounter ‘L’ or ‘R’
4. Whenever the counter returns to 0, it means we have found a balanced substring, so we increment our answer