codility-min-letters-to-be-anagram.java

Solution.java

/**
 * 아나그램이 되기 위해 필요한 최소한의 글자 수
 *
 * An anagram is a word that can be obtained by rearranging the letters of
 * another word, using all the constituent letters exactly once.
 * For example, words "admirer" and "married" are anagrams of one another.
 * However, the words "rather" and "harder" are not anagrams, since "rather"
 * does not contain the letter "d' and "harder" does not contain
 * the letter 't'. Two identical words are anagrams, too.
 * You may also notice that anagram of any word must be of same length as
 * the word itself.
 *
 * Bob has written two words, A and B, consisting of N and M letters,
 * respectively, He would like them to be anagrams of each other.
 * Bob has decided to add some letters to these words to achieve his goal.
 * For example, given the words "rather" and "harder", Bob can add the
 * letter 'd' to the first word and the letter 't' to the second Word.
 * Having done this, the words are now anagrams.
 *
 * Bob would like to add as few letters as possible In the example above,
 * Bob added two letters, which is the minimum possible. Your task is to
 * tell hlm the minimum number of letters that he needs to add to make the
 * given words anagrams in this way.
 *
 * Write a function:
 *     class Solution { public int solution(String a, String b); }
 *
 * that, given two nonempty strings, A and B, consisting of N and M letters
 * respectively, returns the minimum number of letters that Bob has to add
 * to the words specified ln A and B to make them anagrams.
 *
 * For example, given the words "rather" and "harder" your function should
 * return 2, as explained above.
 *
 * For example, given the words "apple" and "pear" your function should
 * return 3, since you can add the letter 'r' to the first word and the
 * letters 'p' and 'l' to the second word to form anagrams.
 *
 * And for the given words "lemon" and "melon", your function should
 * return 0, since the given words are already anagrams.
 *
 * Assume that:
 *     - N and M are integers within the range [1 .. 100,000];
 *     - String ('A', 'B') consists only or lowercase letters (a-z),
 *
 * Complexity:
 *    - expected worst case time complexity is O(N+M);
 *    - expected worst case space complexity ls O(1) (not counting the
 *      storage required for input arguments).
 */

class Solution {
    public int solution(String A, String B) {
        int[] ccA = charCount(A);
        int[] ccB = charCount(B);

        int addA = 0;
        int addB = 0;
        for (int i = 0 ; i < ccA.length ; i++) {
            addA += Math.max(ccB[i] - ccA[i], 0);
            addB += Math.max(ccA[i] - ccB[i], 0);
        }

        //System.out.println(Arrays.toString(ccA) + addA);
        //System.out.println(Arrays.toString(ccB) + addB);

        return addA + addB;
    }

    private int[] charCount(String s) {
        int[] cc = new int['Z' - 'A' + 1]; // 26
        for(int i = 0 ; i < s.length() ; i++) {
            char ch = s.charAt(i);
            if (!('a' <= ch && ch <= 'z')) {
                throw new IllegalArgumentException("Invalid char");
            }
            int ci = ch - 'a';
            cc[ci] += 1;
        }
        return cc;
    }

    // main, test() 는 Codility에서 사용하지 않음
    
    public static void main(String[] args) {
        test("rather", "harder", 2);
        test("apple", "pear", 3);

        test("", "", 0);
        test("", "harder", 6);
        test("harder", "harder", 0);
        test("a", "ab", 1);
        test("coffee", "tuffee", 4);
    }

    private static void test(String A, String B, int expected) {
        int actual = new Solution().solution(A, B);
        if (expected == actual) {
            System.out.print("[+] ");
        } else {
            System.out.print("[-] ");
        }
        System.out.printf("(%s, %s): expected=%d, actual=%d\n", A, B, expected, actual);
    }
}