Split A String In Balanced Strings - Leetcode Solution

Problem Statement: You are given a string s of 'L's and 'R's. A string is said to be balanced if it has an equal number of 'L's and 'R's. You need to split s into the minimum number of balanced strings. Return the minimum number of balanced strings.

Example 1: Input: s = "RLRRLLRLRL" Output: 4 Explanation: s can be split into "RL", "RRLL", "RL", "RL", each substring contains equal number of 'L' and 'R'.

Example 2: Input: s = "RLLLLRRRLR" Output: 3 Explanation: s can be split into "RL", "LLLRRR", "LR", each substring contains equal number of 'L' and 'R'.

Solution: We can solve this problem by scanning the string s from left to right. For each 'L', we increment a counter, and for each 'R', we decrement the counter. When counter becomes 0, we can conclude that the number of 'L's and 'R's are equal so far, and we can split the string into a balanced substring. We repeat this process until we have scanned the entire string s.

The idea behind this algorithm is that every time the counter becomes 0, we have found a balanced string. So we can keep track of the number of balanced strings we have found so far.

Algorithm:

1. Initialize a variable count to 0, and a variable balance to 0.
2. Iterate over each character c in the string s from left to right.
3. If c is 'L', increment balance by 1. If c is 'R', decrement balance by 1.
4. If balance becomes 0, increment count by 1 to indicate that we have found a balanced substring.
5. Return count.

Code:

class Solution: def balancedStringSplit(self, s: str) -> int: count = 0 balance = 0 for c in s: if c == 'L': balance += 1 else: balance -= 1 if balance == 0: count += 1 return count

Time Complexity: O(n) - We only need to scan the string once. Space Complexity: O(1) - We don't use any extra space other than the variables count and balance.

1