Greedy: Given a string, split into balanced strings.

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