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.     // special cases
  36.     if (diffab[n] == 0) {
  37.         cout << "The minimum length of subarray to be removed is: 0";
  38.         return 0;
  39.     }
  40.  
  41.     if (mini == n || mini == 1e9) {  // if full or never updated
  42.         cout << "-1";
  43.         return 0;
  44.     }
  45.  
  46.     cout << "The minimum length of subarray to be removed is: " << mini;
  47.     return 0;
  48. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
3
aab
stdout
copy 
-1
https://ideone.com/zwu1h8
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!