Split a String in Balanced Strings — LeetCode 1221 Python Solution

The 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.

Example

Input

s = "RLRRLLRLRL"

Output

4

Explanation

s can be split into "RL", "RRLL", "RL", "RL", each substring contains same number of 'L' and 'R'.

Python solution

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

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 1221. Split a String in Balanced Strings is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems