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.

`#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 = ((s == '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;        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';    }}`