[HackerRank]變位詞(Anagram)

題目描述

錫德對於閱讀短篇故事很著迷，作為一個電腦科學的學生，他想對這些書做一些分析。他選擇了S1和S2兩個字串，這兩個字串的長度差距小於等於1。你的任務是要找出至少需要更改多少字串S1的字元，才使它跟字串S2是變位詞(Anagram)的關係。

原題網址

輸入格式

第一行為一個整數T，表示有幾組測試資料，範圍在1到100之間(包含1和100)。接下來的T行，每行都是一組測試字串，這個字串是字串S1和字串S2串接起來的結果，長度在1到1000之間0(包含1和10000)，由小寫英文字母組成。

輸出格式

分行輸出每組輸入字串測試的結果。也就是需要更改多少字串S1的字元，才使它跟字串S2是變位詞(Anagram)的關係。

範例輸入

範例輸出

額外解釋

第一組測試中，字串S1為「aaa」，字串S2為「bbb」，所以需要將字串S1改成「bbb」才能跟字串S2是變位詞的關係，共改變了3個字元。

第二組測試中，字串S1為「a」，字串S2為「b」，所以需要將字串S1改成「b」才能跟字串S2是變位詞的關係，共改變了1個字元。

第三組測試中，「abc」的長度是單數，沒辦法切成長度一樣的字串S1和字串S2，它們不可能是變位詞的關係。所以輸出「-1」。

第四組測試中，字串S1為「mn」，字串S2為「op」，所以需要將字串S1改成「op」或是「po」才能跟字串S2是變位詞的關係，共改變了2個字元。

第五組測試中，字串S1為「xy」，字串S2為「yz」，已經是變位詞的關係，不用改變任何字元。

第六組測試中，字串S1為「xaxb」，字串S2為「bbxx」，所以需要至少將字串S1的「a」改成「b」才能跟字串S2是變位詞的關係，共改變了1個字元。

解題概念

所謂的「變位詞(Anagram)」是指由相同數量的字母所排列組合而成的字串，例如「now」和「won」就是變位詞的關係。

在這題由於輸入的測試字串是字串S1和字串S2串接後結果，但由於變位詞的字串長度要相等，因此如果測試字串的長度是單數的話，可以立即知道不管字串S1和字串S2是怎麼切割的，它們一定不是變位詞的關係，直接輸出「-1」即可。

測試字串的前半段為字串S1，剩餘的後半段為字串S2，利用「HashMap」分別記錄它們所包含的字元以及數量。由於是要更改字串S1的字元，所以之後要去找出字串S2擁有的字元，在字串S1中要加多少數量才會跟字串S2中的一樣，把這個數量累加之後就是字串S1至少需要改變的字元數量。

參考答案

import java.util.HashMap;
import java.util.Scanner;
import java.util.Set;

public class Solution {
    
    public static void main(final String[] args) {
        final Scanner sc = new Scanner(System.in);
        
        int t = Integer.parseInt(sc.nextLine());
        while (t-- > 0) {
            final String s = sc.nextLine();
            final int length = s.length();
            if (length % 2 != 0) {
                System.out.println(-1);
            } else {
                int count = 0;
                final int length_half = length / 2;
                final char[] a = s.subSequence(0, length_half).toString().toCharArray();
                final char[] b = s.subSequence(length_half, length).toString().toCharArray();
                final HashMap<Character, Integer> mapA = createMap(a);
                final HashMap<Character, Integer> mapB = createMap(b);
                final Set<Character> keys = mapB.keySet();
                for (final Character c : keys) {
                    final int countB = mapB.get(c);
                    if (mapA.containsKey(c)) {
                        final int countA = mapA.get(c);
                        if(countB > countA){
                            count += countB - countA;
                        }
                    } else {
                        count += countB;
                    }
                }
                System.out.println(count);
            }
        }
    }
    
    public static HashMap<Character, Integer> createMap(final char[] s) {
        final HashMap<Character, Integer> map = new HashMap<>();
        final int length = s.length;
        for (int i = 0; i < length; ++i) {
            final char c = s[i];
            if (map.containsKey(c)) {
                map.put(c, map.get(c) + 1);
            } else {
                map.put(c, 1);
            }
        }
        return map;
    }
}