This problem focuses on splitting a string into the maximum number of balanced substrings. A string is considered balanced if it contains an equal number of ‘L’ and ‘R’ characters. The goal is to iterate through the string and count how many such balanced splits can be formed.
Steps
- Initialize a counter variable to track balance.
- Traverse the string character by character.
- If the character is ‘R’, increment the counter.
- If the character is ‘L’, decrement the counter.
- Whenever the counter becomes zero, it means a balanced substring is found.
- Increment the result count.
- Return the total count.
Dry Run
Input: s = "RLRRLLRLRL"
- R → temp = 1
- L → temp = 0 → count = 1
- R → temp = 1
- R → temp = 2
- L → temp = 1
- L → temp = 0 → count = 2
- R → temp = 1
- L → temp = 0 → count = 3
- R → temp = 1
- L → temp = 0 → count = 4
- Final Answer =
4
Time & Space Complexity
- Time Complexity: O(n), where n is the length of the string
- Space Complexity: O(1), uses constant space
var balancedStringSplit = function(s) {
let temp = 0;
let count = 0;
for(let i = 0; i < s.length; i++) {
if(s[i] == 'R') {
++temp;
} else {
--temp;
}
if(temp == 0) {
++count;
}
}
return count;
};
#include <string>
using namespace std;
class Solution {
public:
int balancedStringSplit(string s) {
int temp = 0, count = 0;
for(char c : s) {
if(c == 'R') temp++;
else temp--;
if(temp == 0) count++;
}
return count;
}
};
int balancedStringSplit(char* s) {
int temp = 0, count = 0;
for(int i = 0; s[i] != '\0'; i++) {
if(s[i] == 'R') temp++;
else temp--;
if(temp == 0) count++;
}
return count;
}
class Solution {
public int balancedStringSplit(String s) {
int temp = 0, count = 0;
for(char c : s.toCharArray()) {
if(c == 'R') temp++;
else temp--;
if(temp == 0) count++;
}
return count;
}
}
class Solution(object):
def balancedStringSplit(self, s):
temp = 0
count = 0
for ch in s:
if ch == 'R':
temp += 1
else:
temp -= 1
if temp == 0:
count += 1
return count
