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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Split a String in Balanced Strings

Number: 1341

Difficulty: Easy

Paid? No

Companies: Amazon, Meta

Problem Description

Given a balanced string s where the number of 'L' and 'R' characters are equal, split it into the maximum number of balanced substrings (each substring having an equal number of 'L' and 'R').

Key Insights

  • A balanced substring has an equal count of 'L' and 'R'.
  • Since the entire string is balanced, we can simply iterate through the string and count the 'L's and 'R's.
  • When the counts become equal, we have a balanced substring and can perform a split.
  • A greedy approach (making a split as soon as a balanced segment is detected) ensures maximal split count.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string
Space Complexity: O(1), as only constant extra space is used

Solution

We use a single counter that is incremented for an 'L' and decremented for an 'R'. By iterating through the string and updating this counter, every time it reaches zero it indicates the end of a balanced substring. We then increment our count of balanced substrings. This greedy strategy ensures that every possible balanced segment is counted as soon as it is identified.

Code Solutions

# Python solution:
def balancedStringSplit(s: str) -> int:
    balance = 0  # Initialize the balance counter
    count = 0    # Initialize the count of balanced substrings
    for char in s:  # Iterate through each character in the string
        if char == 'L':
            balance += 1  # Increment for 'L'
        else:
            balance -= 1  # Decrement for 'R'
        if balance == 0:  # A balanced substring is found whenever the counter is zero
            count += 1
    return count

# Example usage:
s = "RLRRLLRLRL"
print(balancedStringSplit(s))  # Expected output: 4
← Back to All Questions