In this HackerEarth Changes in a string problem solution, You are given a string S of N characters comprising of A's and B's. You can choose any index i and change Si to either A or B.

Find the minimum number of changes that you must make to string S such that the resulting string is of the following format:

 AAAA........BBBB........
 x number of A's n - x number of B's       

where 0 <= x <= n

In other words, your task is to determine the minimum number of changes such that string S has x number of A's in the beginning, followed by the remaining (n - x) number of B's.


HackerEarth Changes in a string problem solution


HackerEarth Changes in a string problem solution.

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

ll t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
string s;
cin>>s;

ll pre[n] = {0};
ll suff[n] = {0};

pre[0] = ((s[0] == 'A') ? 1 : 0);

for(ll i=1;i<n;i++)
pre[i] = pre[i-1] + ((s[i] == 'A') ? 1 : 0);

suff[n-1] = ((s[n-1] == 'B') ? 1 : 0);

for(ll i=n-2;i>=0;i--)
suff[i] = suff[i+1] + ((s[i] == 'B') ? 1 : 0);

ll sum = suff[0];
for(ll i=1;i<n;i++)
sum = max(sum, pre[i-1] + suff[i]);
sum = max(sum, pre[n-1]);

ll ans = n-sum;
cout<<ans<<"\n";
}
return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 14;
int suf[maxn];
int main(){
ios::sync_with_stdio(0), cin.tie(0);
int t;
cin >> t;
while(t--){
int n;
string s;
cin >> n >> s;
suf[n] = 0;
for(int i = n - 1; i >= 0; i--)
suf[i] = (s[i] == 'A') + suf[i + 1];
int pre = 0, ans = n;
for(int i = 0; i <= n; i++){
ans = min(ans, pre + suf[i]);
pre += s[i] == 'B';
}
cout << ans << '\n';
}
}