We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Split a String in Balanced Strings

Difficulty: Easy

Problem Description

Given a balanced string s consisting of characters 'L' and 'R', split it into some number of substrings such that each substring is balanced, i.e., contains an equal quantity of 'L' and 'R' characters. Return the maximum number of balanced strings that can be obtained.

Key Insights

  • A balanced string contains an equal number of 'L' and 'R' characters.
  • To determine how many balanced substrings can be formed, we can use a counting approach.
  • Track the balance of 'L' and 'R' as we iterate through the string.
  • Each time the balance returns to zero, a balanced substring has been formed.

Space and Time Complexity

Time Complexity: O(n) - We traverse the string once. Space Complexity: O(1) - We use a constant amount of space for counters.

Solution

To solve the problem, we can use a greedy approach with a balance counter. We iterate through the string, incrementing the balance for each 'L' and decrementing it for each 'R'. Whenever the balance reaches zero, we have found a balanced substring. We can count how many times the balance reaches zero to determine the maximum number of balanced substrings.

Code Solutions

def maxBalancedStrings(s: str) -> int:
    balance = 0
    count = 0
    for char in s:
        if char == 'L':
            balance += 1
        else:  # char == 'R'
            balance -= 1
        
        # When balance is zero, we found a balanced substring
        if balance == 0:
            count += 1
            
    return count
← Back to All Questions