Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programmingoneonone

HackerEarth Changes in a string problem solution

YASH PAL, 31 July 2024
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';
}
}
coding problems solutions

Post navigation

Previous post
Next post

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes