fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5. // your code goes here
  6. string a;
  7. cin>>a;
  8. int n=a.size();
  9. vector<int>arr(n,0);
  10. unordered_map<int,int>pre; //hashmap contains prefix sum and index
  11. pre[0]=-1;
  12. for(int i=0;i<n;i++){
  13. if(a[i]=='a'){
  14. arr[i]=1;
  15. }
  16. else{
  17. arr[i]=-1;
  18. }
  19. }
  20. int mini=1e9;
  21. int sum=0;
  22. for(int i=0;i<n;i++){
  23. sum+=arr[i];
  24. if(pre.find(sum)!=pre.end()){
  25. int len=i-pre[sum];
  26. mini=min(len,mini);
  27.  
  28. }
  29. pre[sum]=i;
  30. }
  31. cout<<"The minimum subarray that must be removed to get the array with equal count of a and b is:"<<mini;
  32. return 0;
  33. }
Success #stdin #stdout 0s 5296KB
stdin
abbaab
stdout
The minimum subarray that must be removed to get the array with equal count of a and b is:2