HackerEarth Changes in a string problem solution

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[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';
    }
}

coding problems solutions