1221. Split a String in Balanced Strings
Problem Description
A balanced string is a string that contains an equal number of 'L' and 'R' characters. The problem asks to split a given balanced string s
into the maximum number of balanced substrings. A substring is considered balanced if it contains an equal number of 'L' and 'R' characters. The challenge is to find the maximum number of balanced substrings that can be obtained from the input string.
Intuition
To solve this problem, we need to iterate through the string and keep track of the number of 'L' and 'R' characters we've encountered. The idea is to increase a counter every time we encounter 'L' and decrease it every time we encounter 'R'. When this counter returns to zero, it means we have found an equal number of 'L' and 'R' characters, hence a balanced substring.
By initializing a variable l
to zero, we use it as a counter to keep track of the balance between 'L' and 'R' characters. If we encounter 'L', we increment l
, and if we encounter 'R', we decrement l
. Each time l
becomes zero, itās an indication that the substring from the start to the current position is balanced, and we increment our answer ans
by one.
This approach works because we are given that the original string s
is balanced. Therefore, as we process the string from left to right, any time l
is zero, we have found a balanced substring, and we can safely split the string at that point and start counting a new potential balanced substring.
The algorithm ends when we've gone through the entire string, and the final value of ans
is the maximum number of balanced substrings we can obtain.
Learn more about Greedy patterns.
Solution Approach
The implementation of the solution uses a simple but effective algorithm that requires only a single pass through the string. Its simplicity is derived from its reliance on a single integer counter and the characteristics of the string being balanced. Let's walk through the code to understand this better.
In Python, we define a class Solution
with a method balancedStringSplit
that takes a single argument, the string s
. The method is structured as follows:
-
We initialize two integers
ans
andl
to0
.ans
will hold the final count of the balanced substrings, andl
will be used as a counter to track the balance between 'L' and 'R' characters within a substring. -
We iterate over each character
c
in the strings
with afor
loop. -
Inside the loop, we check if
c
is 'L'. If so, we incrementl
, otherwise (meaningc
is 'R'), we decrementl
. -
After updating
l
for the current character, we check ifl
has become0
. If it has, this indicates that we've encountered an equal number of 'L' and 'R' characters up to the current point in the string, forming a balanced substring. We incrementans
to count this new balanced substring. -
Once the loop has finished, we have iterated over the entire string, and
ans
contains the maximum number of balanced substrings we could form.
Here is the Python code that implements this algorithm:
class Solution:
def balancedStringSplit(self, s: str) -> int:
ans = l = 0
for c in s:
if c == 'L':
l += 1
else:
l -= 1
if l == 0:
ans += 1
return ans
There are no additional data structures needed for this solution, and it works in O(n)
time, where n
is the length of the string, because we are making just one pass through it. The space complexity is O(1)
as we are only using a fixed amount of additional space (the two integers ans
and l
).
This algorithm is based on the pattern that a substring is balanced if and only if the number of 'L's is equal to the number of 'R's. Given that the entire string is balanced, we know that each 'L' will eventually be matched by an 'R'. Therefore, the key insight is to count the number of balanced substrings incrementally as we traverse the string.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a simple example to illustrate the solution approach. Suppose we are given the balanced string s = "RLLRRLRL"
. We want to determine the maximum number of balanced substrings we can obtain from this string.
-
We initialize
ans = 0
(the count of balanced substrings) andl = 0
(the balance counter). The strings
is"RLLRRLRL"
. -
As we iterate through the characters of
s
, we apply the following logic:- We encounter 'R':
l
is decremented by 1 (l = -1
). - Next is 'L':
l
is incremented by 1 (l = 0
). - Since
l
is now 0, we have found our first balanced substring "RL".ans
is incremented by 1 (ans = 1
).
- We encounter 'R':
-
Continuing the iteration:
- We encounter 'L':
l
is incremented by 1 (l = 1
). - Next is 'L':
l
is incremented by 1 again (l = 2
). - Then 'R':
l
is decremented by 1 (l = 1
). - And 'R':
l
is decremented by 1 again (l = 0
). - As
l
has returned to 0, we incrementans
by 1 (ans = 2
).
At this stage, we have identified another balanced substring: "LLRR".
- We encounter 'L':
-
For the remaining characters:
- We have 'L': increment
l
by 1 (l = 1
). - Then 'R': decrement
l
by 1 (l = 0
). - Increment
ans
(nowans = 3
) since we've found another balanced substring "LR".
Continuation of the sequence:
- Encounter 'L':
l
is incremented by 1 (l = 1
). - And finally 'R':
l
is decremented back to 0 (l = 0
). - Increment
ans
once more (finalans = 4
) as the last pair "LR" forms a balanced substring.
- We have 'L': increment
-
Now that we've processed the entire string
s
,ans
holds the value 4, which represents the maximum number of balanced substrings.
The substring splits we've found are "RL", "LLRR", "LR", and "LR". Each of these substrings has an equal number of 'L' and 'R' characters, thus meeting the criteria for balanced substrings. The method balancedStringSplit
would return 4 for the input "RLLRRLRL"
, and this concludes our example walkthrough using the solution approach.
Solution Implementation
1class Solution:
2 def balancedStringSplit(self, s: str) -> int:
3 # Initialize count of balanced substrings and a balance counter
4 balanced_count = 0
5 balance = 0
6
7 # Iterate over each character in the string
8 for char in s:
9 # If the character is 'L', increment the balance counter
10 if char == 'L':
11 balance += 1
12 # If the character is 'R', decrement the balance counter
13 else:
14 balance -= 1
15
16 # Check if the substring is balanced
17 if balance == 0:
18 # Increment the count of balanced substrings
19 balanced_count += 1
20
21 # Return the total count of balanced substrings
22 return balanced_count
23
1class Solution {
2 // Method to count the number of balanced strings in the input string 's'.
3 // A balanced string has an equal number of 'L' and 'R' characters.
4 public int balancedStringSplit(String s) {
5 int balanceCount = 0; // To store the number of balanced strings found
6 int balance = 0; // A variable to track the balance between 'L' and 'R' characters
7
8 // Loop through each character in the string
9 for (char c : s.toCharArray()) {
10 // Increment balance when 'L' is found
11 if (c == 'L') {
12 balance++;
13 // Decrement balance when 'R' is found
14 } else if (c == 'R') {
15 balance--;
16 }
17
18 // When balance is zero, a balanced string is found
19 if (balance == 0) {
20 balanceCount++;
21 }
22 }
23
24 // Return the total number of balanced strings
25 return balanceCount;
26 }
27}
28
1class Solution {
2public:
3 // This function counts how many times the input string can be split
4 // into balanced strings, where "balanced" means the number of 'L's and 'R's
5 // in the substring are equal.
6 int balancedStringSplit(string s) {
7 int countBalanced = 0; // To keep track of the count of balanced strings
8 int balanceFactor = 0; // To keep track of the balance between 'L' and 'R'
9
10 // Iterate over each character in the string
11 for (char c : s) {
12 // Increment balance factor for 'L' and decrement for 'R'
13 if (c == 'L') {
14 balanceFactor++;
15 } else { // c == 'R'
16 balanceFactor--;
17 }
18
19 // When the balance factor is zero, we have a balanced string
20 if (balanceFactor == 0) {
21 countBalanced++; // Increment the number of balanced strings
22 }
23 }
24
25 // Return the total number of balanced strings
26 return countBalanced;
27 }
28};
29
1/**
2 * Function to count the number of balanced strings that can be split.
3 * Balanced strings are those where the quantity of 'L' and 'R' characters is the same.
4 *
5 * @param {string} inputString - The string to be checked for balanced splits.
6 * @return {number} - The count of balanced strings that can be split.
7 */
8const balancedStringSplit = (inputString: string): number => {
9 let balancedCount = 0; // Counter for balanced splits
10 let balance = 0; // Helper to keep track of the current balance between 'L' and 'R'
11
12 // Iterate through the string to check for balanced segments.
13 for (let character of inputString) {
14 balance += (character == 'L') ? 1 : -1;
15 // If balance is 0, a balanced segment is found.
16 if (balance === 0) {
17 balancedCount++;
18 }
19 }
20
21 return balancedCount; // Return the total number of balanced strings.
22};
23
24// Example usage:
25// let result = balancedStringSplit("RLRRLLRLRL");
26// console.log(result); // Outputs: 4, because there are four balanced substrings "RL", "RRLL", "RL", "RL"
27
Time and Space Complexity
Time Complexity
The time complexity of the code is O(n)
, where n
is the length of the input string s
. This is because the code iterates through each character in the string exactly once, performing a constant amount of work for each character with simple arithmetic operations and a comparison.
Space Complexity
The space complexity of the code is O(1)
. The code uses a fixed number of integer variables (ans
and l
) regardless of the input size. These variables take up a constant amount of space and do not scale with the size of the input string.
Learn more about how to find time and space complexity quickly using problem constraints.
How does merge sort divide the problem into subproblems?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!