fork download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. class Codechef
  6. {
  7. 	public static void main (String[] args) throws java.lang.Exception
  8. 	{
  9. 		// your code goes here
  10. 		Scanner sc = new Scanner(System.in);
  11. 		int t = sc.nextInt();
  12. 		while (t-- > 0) {
  13. 		    int n = sc.nextInt();
  14. 		    String st = sc.next();
  15.  
  16. 		    int ans=solve(st);
  17. 		    System.out.println(ans);
  18. 		}
  19. 		sc.close();
  20. 	}
  21.  
  22. 	public static int solve(String str){
  23. 	    int n=str.length();
  24. 	    int ta=0,tb=0;
  25.  
  26. 	    for(int i=0;i<n;i++){
  27. 	        if(str.charAt(i)=='a'){
  28. 	            ta++;
  29. 	        }
  30. 	        if(str.charAt(i)=='b') {
  31. 	            tb++;
  32. 	        }
  33. 	    }
  34. 	    if (ta == tb) return 0;
  35.         if (ta == 0 || tb == 0) return -1;
  36.  
  37. 	    int imbalanceFactor = ta-tb;
  38. 	    Map<Integer, Integer> map = new HashMap<>();
  39.  
  40.         int prefix = 0;
  41.         int minLen = Integer.MAX_VALUE;
  42.  
  43.         map.put(0, -1); 
  44.  
  45.         for (int i = 0; i < n; i++) {
  46.             if(str.charAt(i)=='a'){
  47.                 prefix+=1;
  48.             }else{
  49.                 prefix-=1;
  50.             }
  51.  
  52.             if (map.containsKey(prefix - imbalanceFactor)){
  53.                 minLen = Math.min(minLen, i - map.get(prefix - imbalanceFactor));
  54.             }
  55.             if(!map.containsKey(prefix)){
  56.                 map.put(prefix, i);
  57.             }
  58.  
  59.         }
  60.  
  61.         if (minLen == Integer.MAX_VALUE) return -1;
  62.         if (minLen == n) return -1; 
  63.         return minLen;
  64.  
  65. 	}
  66. }
  67.  
Success #stdin #stdout 0.14s 54624KB
comments (?)
stdin
copy 
5
5
bbbab
6
bbaaba
4
aaaa
12
aabbaaabbaab
5
aabaa
stdout
copy 
3
0
-1
2
-1
https://ideone.com/dp8TJS
language:
Java (HotSpot 12)
created:
5 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!