# Split a String in Balanced Strings
**Difficulty:** EASY
[External](https://leetcode.com/problems/split-a-string-in-balanced-strings)
Canonical: https://scaleengineer.com/dsa/problems/split-a-string-in-balanced-strings
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** String
---
## 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'.

**Example 2:**

**Input:** s = "RLRRRLLRLL"
**Output:** 2
**Explanation:** s can be split into "RL", "RRRLLRLL", each substring contains same number of 'L' and 'R'.
Note that s cannot be split into "RL", "RR", "RL", "LR", "LL", because the 2nd and 5th substrings are not balanced.

**Example 3:**

**Input:** s = "LLLLRRRR"
**Output:** 1
**Explanation:** s can be split into "LLLLRRRR".

**Constraints:**

* `2 <= s.length <= 1000`
* `s[i]` is either `'L'` or `'R'`.
* `s` is a **balanced** string.

# Approaches
## Dynamic Programming
This approach uses dynamic programming to find the optimal number of splits. We build a solution from smaller subproblems. Let `dp[i]` be the maximum number of balanced substrings we can split the prefix of length `i` (i.e., `s.substring(0, i)`) into. To calculate `dp[i]`, we try all possible split points `j` before `i`. If the substring from `j` to `i` is balanced, we can make a split there, and the total number of splits would be `1 + dp[j]`. We take the maximum over all possible valid `j`'s.
**Time:** O(n^2), where n is the length of the string. The nested loops lead to a quadratic time complexity. The outer loop runs `n` times, and the inner loop can run up to `n` times. · **Space:** O(n), where n is the length of the string. We use a DP array of size `n + 1` to store the results for subproblems.
**Pros:** It is a systematic approach that guarantees finding the optimal solution.; The DP pattern is general and can be adapted for other similar string splitting problems.
**Cons:** Significantly less efficient in terms of time complexity compared to the greedy approach.; Requires extra space proportional to the input string length.; The logic is more complex to implement and reason about for this particular problem.
### Explanation
The core of this method is the recurrence relation: `dp[i] = max(1 + dp[j])` for all `0 <= j < i` such that the substring `s.substring(j, i)` is balanced. We need to build a `dp` table of size `n+1`. The base case is `dp[0] = 0`, as an empty string has zero splits. We then iterate from `i = 1` to `n`. For each `i`, we iterate backwards from `j = i - 1` to `0`. In this inner loop, we keep track of the balance of 'L' and 'R' characters for the substring `s.substring(j, i)`. Whenever we find that this substring is balanced, we use the pre-computed result for the prefix of length `j` (stored in `dp[j]`) to update `dp[i]`. The final answer is the value stored in `dp[n]`. 

```java
class Solution {
    public int balancedStringSplit(String s) {
        int n = s.length();
        int[] dp = new int[n + 1];
        // dp[i] stores the max number of balanced strings for prefix s[0...i-1]
        
        for (int i = 1; i <= n; i++) {
            int countL = 0;
            int countR = 0;
            // Iterate backwards to check all possible last substrings s[j...i-1]
            for (int j = i - 1; j >= 0; j--) {
                if (s.charAt(j) == 'L') {
                    countL++;
                } else {
                    countR++;
                }
                // Check if the substring s[j...i-1] is balanced
                if (countL > 0 && countL == countR) {
                    // We can form a split here. The total splits would be
                    // 1 (for the current substring) + dp[j] (for the prefix)
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[n];
    }
}
```
### Algorithm
*   Initialize a DP array `dp` of size `n + 1`, where `n` is the length of the string `s`. `dp[i]` will store the maximum number of balanced string splits for the prefix `s.substring(0, i)`.
*   Set `dp[0] = 0` (an empty string has 0 splits) and initialize the rest of `dp` array to 0.
*   Iterate `i` from 1 to `n` to compute `dp[i]` for each prefix length.
*   For each `i`, start an inner loop with `j` from `i - 1` down to 0. This inner loop checks every possible last substring `s.substring(j, i)`.
*   Inside the inner loop, maintain the counts of 'L' and 'R' characters for the substring `s.substring(j, i)`.
*   If the counts become equal (and are not zero), it means `s.substring(j, i)` is a balanced string. We can then potentially form a split. The total number of splits would be `1 + dp[j]`.
*   Update `dp[i]` with the maximum value found: `dp[i] = Math.max(dp[i], 1 + dp[j])`.
*   After the loops complete, `dp[n]` will hold the maximum number of splits for the entire string `s`.

## Greedy Single Pass
The most efficient way to solve this problem is with a greedy approach. We can iterate through the string with a single pass, keeping track of the balance between 'L' and 'R' characters. To maximize the number of substrings, we should make a split as soon as we can. A split is possible whenever the count of 'L's and 'R's is equal in the prefix we have scanned since the last split. Because the entire string is balanced, this greedy choice is always optimal; finding a balanced prefix guarantees the remaining suffix is also balanced, so we can solve the problem for the suffix independently.
**Time:** O(n), where n is the length of the string. We iterate through the string only once. · **Space:** O(1). We only use a couple of integer variables for counting, which does not depend on the size of the input string.
**Pros:** Extremely efficient with O(n) time complexity.; Uses constant extra space, making it very memory-efficient.; The logic is simple, intuitive, and easy to implement correctly.
**Cons:** This greedy approach is highly specific to this problem's constraints and properties (e.g., the input string itself is balanced) and may not generalize to other problems.
### Explanation
We use a single variable, let's call it `balance`, initialized to zero. We iterate through the input string `s`. When we encounter an 'L', we increment `balance`, and when we see an 'R', we decrement it. Any time `balance` returns to zero, it signifies that we have processed a substring containing an equal number of 'L's and 'R's. This is the shortest possible balanced prefix at that point. We count this as one valid split and continue the process for the rest of the string. The `balance` counter effectively resets for the next segment automatically.

```java
class Solution {
    public int balancedStringSplit(String s) {
        int resultCount = 0;
        int balance = 0;
        
        for (char c : s.toCharArray()) {
            if (c == 'L') {
                balance++;
            } else { // c == 'R'
                balance--;
            }
            
            // If balance is 0, we found a balanced substring
            if (balance == 0) {
                resultCount++;
            }
        }
        
        return resultCount;
    }
}
```
### Algorithm
*   Initialize a counter for the number of splits, `resultCount`, to 0.
*   Initialize a `balance` variable to 0. This variable will track the running balance of 'L' and 'R' characters.
*   Iterate through the string `s` from left to right, character by character.
*   For each character, if it's an 'L', increment `balance`. If it's an 'R', decrement `balance` (or vice-versa, as long as it's consistent).
*   After updating `balance` in each step, check if `balance` has become 0.
*   If `balance == 0`, it means we have just completed a balanced substring. Increment `resultCount`.
*   After the loop finishes, `resultCount` will hold the maximum number of balanced substrings.

# Solutions
### Java

```java
class Solution { public int balancedStringSplit ( String s ) { int ans = 0 , l = 0 ; for ( char c : s . toCharArray ()) { if ( c == 'L' ) { ++ l ; } else { -- l ; } if ( l == 0 ) { ++ ans ; } } return ans ; } }
```

### JavaScript

```javascript
/** * @param {string} s * @return {number} */ var balancedStringSplit =
  function (s) {
    let ans = 0;
    let l = 0;
    for (let c of s) {
      if (c == " L ") {
        ++l;
      } else {
        --l;
      }
      if (l == 0) {
        ++ans;
      }
    }
    return ans;
  };

```

### CPP

```cpp
class Solution { public: int balancedStringSplit ( string s ) { int ans = 0 , l = 0 ; for ( char c : s ) { if ( c == 'L' ) ++ l ; else -- l ; if ( l == 0 ) ++ ans ; } return ans ; } };
```

### Python

```python
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
```