Problem Statement:
You are given a string with “R” “L” characters.
You need to balance the string so that it will have same number of R and L.
Return the maximum number of split balanced strings.
Example
Input: s = "RLRRLLRLRL" Output: 4 String can be split into "RL", "RRLL", "RL", "RL"
Solution
We can solve this problem with the help of greedy approach
Linearly count the R and L. Then if both R and L count matches, then increment the answer and reset R and L values.
Solution in C++
#include<iostream> #include<vector> #include<algorithm> #include<string> #include<unordered_map> using namespace std; int balanced_string_split(string s) { int ans=0, n=s.size(), l=0, r=0; for(int i=0; i<n; i++) { if(s[i]=='R') r++; else l++; if(r==l) { ans++; l = 0, r = 0; } } return ans; } int main() { string str = "RLRRLLRLRL"; cout<<"The string can be split into "<< balanced_string_split(str)<<" times"<<endl; return 0; }
Output:
The string can be split into 4 times