Scale Engineer

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

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];    }}

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.

Solutions

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

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 →

Next problem