Strings: Making Anagrams

  • + 0 comments

    Java15 solution that passes all test cases. Three HashMaps and a dream...

    public static int makeAnagram(String a, String b) {
        int count = 0;
        
        HashMap<Character, Integer> aCharFreq = new HashMap<Character, Integer>();
        HashMap<Character, Integer> bCharFreq = new HashMap<Character, Integer>();
        HashMap<Character, Integer> toDelCharFreq = new HashMap<Character, Integer>();
        
        for (int i = 0; i < a.length(); i++) { //Get the character frequencies for string a.
            char c = a.charAt(i);
            if (aCharFreq.containsKey(c)) aCharFreq.replace(c, aCharFreq.get(c) + 1);
            else aCharFreq.put(c, 1);
        }
        
        for (int i = 0; i < b.length(); i++) { //Get the character frequencies for string b.
            char d = b.charAt(i);
            if (bCharFreq.containsKey(d)) bCharFreq.replace(d, bCharFreq.get(d) + 1);
            else bCharFreq.put(d, 1);
        }
        
        for (char keyA : aCharFreq.keySet()) { //Now check the character frequencies for string a.
            if (bCharFreq.containsKey(keyA)) toDelCharFreq.put(keyA,Math.abs(bCharFreq.get(keyA) - aCharFreq.get(keyA))); //If b contains the character in a that we're looking at, add the difference between the number of times that character shows up in b and a.
            else toDelCharFreq.put(keyA,aCharFreq.get(keyA)); //Add every character that shows up in a but not b.
        }
                
        for (char keyB : bCharFreq.keySet()) { //Then check the character frequencies for string b.
            if (aCharFreq.containsKey(keyB) && toDelCharFreq.get(keyB) == 0) toDelCharFreq.remove(keyB); //If a and b have an equal number of instances of a character, that character will be part of the anagram set and must be removed from the target character frequencies.
            else if (!aCharFreq.containsKey(keyB)) toDelCharFreq.put(keyB,bCharFreq.get(keyB)); //Add every character that shows up in b but not a.
        }
        
        for (char key : toDelCharFreq.keySet()) count += toDelCharFreq.get(key); //Finally, add up the frequencies of all characters remaining to get the retur value.
        
        return count;
    }