Split a String in Balanced Strings

Easy Subject: Greedy

Time Complexity

O(N)

Space Complexity

O(1)

Problem Description

Problem Statement

Balanced strings are those that have an equal quantity of 'L' and 'R' characters. Given a balanced string s, split it into the maximum amount of balanced strings.

Example 1:

Input: s = "RLRRLLRLRL"
Output: 4

Optimal Solution

Python

Approach: Greedy Counter

Iterate through the string, maintaining a balance counter. Increment for 'L', decrement for 'R'. Every time the balance returns to 0, we have found a balanced substring, so we increment our result count.

class Solution:
    def balancedStringSplit(self, s: str) -> int:
        balance = 0
        count = 0

        for char in s:
            if char == 'L':
                balance += 1
            else:
                balance -= 1

            if balance == 0:
                count += 1

        return count