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=0;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. 	if(diffab[n]==0){      //already balanced
  35. 		mini=0;          
  36. 	}
  37. 	if(mini==n){     //need to remove whole string
  38. 		cout<<"-1";
  39. 	}
  40. 	cout<<"The minimum length of subarray to be removed is:"<<mini;
  41. 	return 0;
  42. }
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
3
aab
stdout
copy 
-1The minimum length of subarray to be removed is:1
https://ideone.com/NgOcX0
language:
C++ (gcc 8.3)
created:
3 days 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!