algoadvance

The problem is taken from LeetCode, and it states:

1221. Split a String in Balanced Strings

Balanced strings are those that have an equal quantity of ‘L’ and ‘R’ characters.

Given a balanced string s, split it into the maximum number of balanced strings.

Return the maximum number of balanced strings.

Example:

• 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 = "RLLLLRRRLR"
  Output: 3
  Explanation: s can be split into "RL", "LLLRRR", "LR", each substring contains same number of 'L' and 'R'.
  

• Example 3:

  Input: s = "LLLLRRRR"
  Output: 1
  Explanation: s can be split into "LLLLRRRR".
  

Constraints:

• 1 <= s.length <= 1000
• s[i] is either ‘L’ or ‘R’.
• s is a balanced string.

Clarifying Questions

1. Can the string contain characters other than ‘L’ and ‘R’?
   • No, the string will only contain ‘L’ and ‘R’.
2. Is the input guaranteed to be a balanced string?
   • Yes, the input string s is guaranteed to be balanced.

Strategy

1. Initialize Counters:
   • Use a counter to track the balance of ‘L’ and ‘R’. Initialize it to 0.
   • Use another counter to keep track of the number of balanced strings.
2. Iterate Through String:
   • For each character in the string:
     • Increment the balance counter if the character is ‘R’.
     • Decrement the balance counter if the character is ‘L’.
   • Whenever the balance counter reaches 0, increment the count of balanced strings.
3. Return Result:
   • Return the count of balanced strings.

Time Complexity

The time complexity of this algorithm is O(n) where n is the length of the input string s. This is because we iterate through the string once. The space complexity is O(1) since we are using a constant amount of extra space.

Code

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

# Example usage
example_input_1 = "RLRRLLRLRL"
print(balancedStringSplit(example_input_1))  # Output: 4

example_input_2 = "RLLLLRRRLR"
print(balancedStringSplit(example_input_2))  # Output: 3

example_input_3 = "LLLLRRRR"
print(balancedStringSplit(example_input_3))  # Output: 1

This code effectively splits the given string into the maximum number of balanced substrings by maintaining a running balance of ‘L’ and ‘R’ characters and incrementing the split count every time this balance reaches zero.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?