Balanced strings are those that have an equal quantity of 'L' and 'R' characters.
Given a balanced string s, split it into some number of substrings such that:
Return the maximum number of balanced strings you can obtain.
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 = "RLRRRLLRLL" Output: 2 Explanation: s can be split into "RL", "RRRLLRLL", each substring contains same number of 'L' and 'R'. Note that s cannot be split into "RL", "RR", "RL", "LR", "LL", because the 2nd and 5th substrings are not balanced.
Example 3:
Input: s = "LLLLRRRR" Output: 1 Explanation: s can be split into "LLLLRRRR".
Constraints:
2 <= s.length <= 1000s[i] is either 'L' or 'R'.s is a balanced string.This approach uses a single pass through the string while maintaining a balance counter. Start with a balance of 0 and traverse the string. Increment the balance by 1 for an 'R' and decrement it by 1 for an 'L'. Every time the balance equals zero, it means we have found a balanced substring. Increase the count of balanced substrings at these points.
This C program reads a string and splits it into balanced strings by iterating and using a balance counter. 'R' increments the balance, while 'L' decrements it. Upon reaching a balance of zero, a balanced string is counted.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the string. The function makes a single pass through the string.
Space Complexity: O(1), as only a few variables are used regardless of the input size.
This approach involves using two separate counters specifically counting 'L' and 'R'. As we traverse the string, increment the respective counter for 'L' and 'R'. Whenever the two counters are equal, it indicates a balanced substring.
This C solution uses separate counters for 'L' and 'R', checking for equality to indicate balanced substrings. On equal counts, it resets the counters.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Greedy Approach Using Counter | Time Complexity: O(n), where n is the length of the string. The function makes a single pass through the string. |
| Two Counter Method | Time Complexity: O(n) |
Split a String in Balanced Strings • Kevin Naughton Jr. • 29,652 views views
Watch 9 more video solutions →Practice Split a String in Balanced Strings with our built-in code editor and test cases.
Practice on FleetCode