Minimum number of steps to make string a good string :
Given a string with characters a and b.A string is called good if it doesnot contain substring “ab”.If we have substring “ab” we should replace it with string “bba”.Find the minimum number of steps to make the given string a good string
Input : aaba
Output :
3
explanation
1st
step->abbaa("ab" index 1,2 original stringis replaced with "bba")
string index starts at 0
2nd
step->bbabaa("ab" index 0,1 updated string is replaced with "bba")
3rd
step->bbbbaaa("ab" index 2,3 updated string is replaced with "bba")
Input : abb
Output : 2
explanation
1st
step->bbab("ab" index 0,1 from original stringis replaced with "bba")
string index starts at 0
2nd
step->bbbba("ab" index 2,3 from updated string is replaced with "bba")
This solution can be solved greedily.The string is called good if bbbbbaaaa (b followed by a) .so we will start traversing from the right when we encountered the character ‘a’ we will add to the counter no of b’s to the right.we will double the number of ‘b’s because we are replacing with “bba”.
Implementation :
#include <iostream>
#include<string.h>
using namespace std;
int cal(string &s)
{
//intialize sum and count of b's to right of a
int sum=0;
//count number of b's to right of a
int c=0;
//size of string
int n=s.size();
//travesing the string from back
for(int i=n-1;i>=0;i--)
{ //when we encountered 'b' we will increment the count
if(s[i]=='b')
c++;
else
{
sum=sum+c;
//we are doubling the number of 'b's
c=c*2;
}
}
return sum;
}
//driver code
int main() {
string s="aaba";
cout<<"Minimum number of steps to make string a good string "<<cal(s)<<endl;
return 0;
}
