Split a String in Balanced Strings

Easy

#1140Time: 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.

Patterns

Greedy Counting

Data structures

String

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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

1class Solution {2    public int balancedStringSplit(String s) {3        int n = s.length();4        int[] dp = new int[n + 1];5        // dp[i] stores the max number of balanced strings for prefix s[0...i-1]6        7        for (int i = 1; i <= n; i++) {8            int countL = 0;9            int countR = 0;10            // Iterate backwards to check all possible last substrings s[j...i-1]11            for (int j = i - 1; j >= 0; j--) {12                if (s.charAt(j) == 'L') {13                    countL++;14                } else {15                    countR++;16                }17                // Check if the substring s[j...i-1] is balanced18                if (countL > 0 && countL == countR) {19                    // We can form a split here. The total splits would be20                    // 1 (for the current substring) + dp[j] (for the prefix)21                    dp[i] = Math.max(dp[i], dp[j] + 1);22                }23            }24        }25        return dp[n];26    }27}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1class Solution {2    public int balancedStringSplit(String s) {3        int resultCount = 0;4        int balance = 0;5        6        for (char c : s.toCharArray()) {7            if (c == 'L') {8                balance++;9            } else { // c == 'R'10                balance--;11            }12            13            // If balance is 0, we found a balanced substring14            if (balance == 0) {15                resultCount++;16            }17        }18        19        return resultCount;20    }21}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class 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 ; } }

1/** * @param {string} s * @return {number} */ var balancedStringSplit =2  function (s) {3    let ans = 0;4    let l = 0;5    for (let c of s) {6      if (c == " L ") {7        ++l;8      } else {9        --l;10      }11      if (l == 0) {12        ++ans;13      }14    }15    return ans;16  };

1class 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 ; } };

1class 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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem