Domain 1EasyCORE

Split a String in Balanced Strings

The problem requires us to split a given balanced string `s` into the maximum number of balanced substrings. A balanced substring is defined as one that contains an equal number of 'L' and 'R' characters.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#String#Greedy

1221. Split a String in Balanced Strings

Model: qwen2.5-coder:14b
Topics: String,Greedy
FAANG asked: 0
Acceptance rate: 84.3%


Problem Breakdown

The problem requires us to split a given balanced string s into the maximum number of balanced substrings. A balanced substring is defined as one that contains an equal number of ‘L’ and ‘R’ characters.

Inputs:

  • A single string s consisting of ‘L’ and ‘R’ characters.
  • The length of s is between 1 and 1000, inclusive.
  • It is guaranteed that the input string s is balanced, meaning it can be split into at least one balanced substring.

Outputs:

  • An integer representing the maximum number of balanced substrings that s can be split into.

Implicit Constraints or Tricky Edge Cases:

  • The string length constraint is manageable (up to 1000), so we don’t need to worry about overflow.
  • Since the input string is guaranteed to be balanced, we don’t need to handle cases where the string cannot be split into balanced substrings.

Intuition

A brute-force approach would involve checking all possible substrings of s to see if they are balanced and counting them. However, this approach would have a high time complexity (O(n^2)) due to the nested loops required for substring generation and balance checking.

The key insight is that we can use a greedy approach to solve this problem efficiently. We can iterate through the string while maintaining a count of ‘L’ and ‘R’ characters. Whenever the counts are equal, it indicates that we have found a balanced substring. This approach ensures that we find the maximum number of balanced substrings in a single pass through the string.

Approach

  1. Initialize two variables: balance to keep track of the difference between the count of ‘L’ and ‘R’ characters, and result to count the number of balanced substrings.
  2. Iterate through each character in the string:
    • If the character is ‘L’, increment the balance.
    • If the character is ‘R’, decrement the balance.
    • Whenever balance becomes zero, it means we have found a balanced substring. Increment the result.
  3. Return the result after processing all characters in the string.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the string s. We make a single pass through the string.
  • Space Complexity: O(1). We use only a constant amount of extra space for variables balance and result.

Solution

def balancedStringSplit(s: str) -> int:
    balance = 0
    result = 0
    
    for char in s:
        if char == 'L':
            balance += 1
        else:
            balance -= 1
        
        if balance == 0:
            result += 1
    
    return result

Edge Cases Handled

  • The code handles the case where the string length is at its minimum (1) and maximum (1000).
  • Since the input string is guaranteed to be balanced, the code will always find at least one balanced substring.
  • The code efficiently processes the string in a single pass, ensuring optimal performance even for the upper constraint of 1000 characters.