← 都来码 / Dolaima← 例程索引java/school/Anagram.java 原文

java/school/Anagram.java · 1341 字节 · 下载原文

// https://www.hackerrank.com/challenges/anagram

/*
	Used counting sort to get count of each alphabet,
	
	Time Complexity - O(n) - O(n) for parsing and counting string and then O(26) for get the count from the array
	Space Complexity - O(1) - O(26 + 26) for storing the count of alphabets.
*/

import java.util.Scanner;

class Anagram {
	
	public static int countAnagramDiff(String s) {
		if(s.length() % 2 == 0) {
			
			int half = s.length()/2;
			int[] stringArr1 = new int[26];
			int[] stringArr2 = new int[26];
			
			for(int i = 0; i < half; i++) {
				stringArr1[s.charAt(i) - 97]++;
			}
			for(int i = half; i < s.length(); i++) {
				stringArr2[s.charAt(i) - 97]++;
			}
			
			/*
			for(int i = 0; i < 26; i++) {
				System.out.print(" " + stringArr1[i]);
			}
			System.out.println();
			for(int i = 0; i < 26; i++) {
				System.out.print(" " + stringArr2[i]);
			}
			*/
			
			int count = 0;
			for(int i = 0; i < 26; i++) {
				if(stringArr1[i] > stringArr2[i]) {
					count += stringArr1[i] - stringArr2[i];
				}
			}
			
			return count;
		} else {
			return -1;			
		}
	}
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		int T = in.nextInt();
		
		while(T-- > 0) {
			String input = in.next();
			
			//System.out.println();
			System.out.println(countAnagramDiff(input));
		}
	}
}