Java | Frequency Counting | Fully Explained | Must Read
Note: there are multiple interesting ways to solve this problem. This is just one of them.\n\n# Intuition\nTo have a valid palindrome we must have a prefix matc
Note: there are multiple interesting ways to solve this problem. This is just one of them.\n\n# Intuition\nTo have a valid palindrome we must have a `prefix` matching a `reversed suffix` up to the middle of the word. So if we choose to take some word from the `words` array, we must make sure we can append that word in a reversed order at the end of the palindrome.\n\nExample: if we decide to take `"ab"` into our palindrome we must make sure there is an `"ba"` that we can append in the suffix (or vice-versa, the order doesn\'t matter)\n\nIf a word is composed of the same characters, for example "aa" we must append "aa" in the suffix too. The reverse of that word is the same word, so we must find at least 2 occurrences of it.\n\nNow we can also find a word with the same characters, but without a matching pair. In that case we can only append `1 such word` in the middle of our palindrome. Example: `xxxAAxxx`.\n\n# Algorithm\nWe are going to count the frequency of words in `words` array.\n\nIf the word equals it\'s reversed word (aa = aa) then we take all the pairs we can match. If we had 3 occurrences of aa, we can take 2 pairs. (remember we must take a pair to append as a prefix and suffix).\n\nThen we also check if we have a left over to append in the middle.\n\nIf the word doesn\'t equal the reversed word, we must check if we have the reversed word in the `frequency map`. If we do we take the minimum number of pairs of the two `Math.min(freq(word), freq(rev_word))`\n\n# Code\n```\n    class Solution {\n        public int longestPalindrome(String[] words) {\n            Map<String, Long> wordFreq = Arrays\n                    .stream(words)\n                    .collect(\n                            Collectors.groupingBy(x -> x, Collectors.counting())\n                    );\n\n            int result = 0;\n            boolean foundLeftOut = false;\n            for (String word : wordFreq.keySet()) {\n                String reverseWord = reverse(word);\n\n                Long occurrencesOfWord = wordFreq.get(word);\n                if (word.equals(reverseWord)) {\n                    result += 4 * (occurrencesOfWord / 2); // Take all pairs you can\n                    if (occurrencesOfWord % 2 == 1) foundLeftOut = true; // if remainder left\n                    continue;\n                }\n\n                // Not same word\n                if (wordFreq.containsKey(reverseWord) && wordFreq.get(reverseWord) > 0) {\n                    long pairsToTake = Math.min(wordFreq.get(word), wordFreq.get(reverseWord));\n                    \n                    result += 4 * pairsToTake;\n                    wordFreq.put(word, wordFreq.get(word) - pairsToTake);\n                    wordFreq.put(reverseWord, wordFreq.get(reverseWord) - pairsToTake);\n                }\n\n            }\n            return foundLeftOut ? result + 2 : result;\n        }\n\n        private String reverse(String word) {\n            return new StringBuilder(word).reverse().toString();\n        }\n    }\n```
['Java']