Split a String in Balanced Strings

easy string greedy counter

Problem

A string is balanced if it has an equal number of 'L' and 'R' characters. Given a balanced string s, split it into the maximum number of balanced substrings and return that count.

Inputs = "RLRRLLRLRL"

Output4

Splits into "RL", "RRLL", "RL", "RL", each with equal L and R.

s (only L and R)

def balanced_string_split(s):
    count = 0
    balance = 0
    for c in s:
        balance += 1 if c == 'L' else -1
        if balance == 0:
            count += 1
    return count

function balancedStringSplit(s) {
  let count = 0;
  let balance = 0;
  for (const c of s) {
    balance += c === 'L' ? 1 : -1;
    if (balance === 0) count++;
  }
  return count;
}

class Solution {
    public int balancedStringSplit(String s) {
        int count = 0;
        int balance = 0;
        for (char c : s.toCharArray()) {
            balance += (c == 'L') ? 1 : -1;
            if (balance == 0) count++;
        }
        return count;
    }
}

int balancedStringSplit(string s) {
    int count = 0;
    int balance = 0;
    for (char c : s) {
        balance += (c == 'L') ? 1 : -1;
        if (balance == 0) count++;
    }
    return count;
}

Explanation

A string is balanced when it has equal numbers of 'L' and 'R'. To get the maximum number of balanced pieces, the greedy trick is to cut a piece off the moment it becomes balanced rather than waiting.

We keep a single running balance counter: add +1 for every 'L' and -1 for every 'R'. Whenever this counter hits 0, the characters since the last cut have equal L and R, so we close a balanced substring and increase count.

This works because the smallest balanced chunks let us make the most cuts, and any balanced string can be broken at every zero-crossing without leaving leftovers.

Example: s = "RLRRLLRLRL". Reading along, balance returns to 0 after RL, then again after RRLL, then after RL, then after RL — that is 4 balanced pieces.

Since we never skip a zero-crossing, the count we collect is the maximum number of balanced substrings.

Time: O(n) Space: O(1)