Java || 👍Explained in Detail👍|| Simple & Fast Solution✅|| Counting || Hash Table || Greedy
I do my best everyday to give a clear explanation, so to help everyone improve their skills.\n\nIf you find this helpful, please \uD83D\uDC4D upvote this post a
I do my best everyday to give a clear explanation, so to help everyone improve their skills.\n\nIf you find this **helpful**, please \uD83D\uDC4D **upvote** this post and watch my [Github Repository](https://github.com/cheehwatang/leetcode-java).\n\nThank you for reading! \uD83D\uDE04 Comment if you have any questions or feedback.\n\n---\n\n## Approach\n\nThis problem has two fundamental cases:\n1. Word with 2 different character (eg. "ab", "cd")\n2. Word with same characters (eg. "aa", "bb")\n\nCase 1:\nWe need to find the pair that matches each other in a palindrome. For example using words "ab" and "ba".\nThey can form a palindrome by either "abba" or "baab". Even if we have other palindromes in between, it does not affect, such as "abXXXXba" or "baXXXXab".\nWith that, we need to store the occurrence of either "ab" or "ba", whichever came first. Then the next word can be flipped and checked.\nAs the pair is "used" as soon as matched, this is a greedy approach.\n\nCase 2:\nThis can further split into 2 behaviors.\nFirst is the same as Case 1, "aa" and "aa" forming "aaaa" palindrome.\nSecond is for it to be in the center of the palindrome.\nFor example, words are "ab", "ba" and "zz", it can form "abzzba".\nAs such, we need to first check the case 1 behavior.\nIf any word with same characters still remains, increase the result by 2.\n\nFor both cases, we can either use a counting array (size 26 * 26) for the lowercase English letters, or use a Hash Map.\nIf the strings has more characters and longer length, then counting approach would not work.\n\n## Complexity\n- Time Complexity = $$O(n)$$, where $$n$$ is the length of String[] words.\n- Space Complexity = $$O(1)$$,\n  or $$O(26 * 26)$$, which is constant space for the Counting approach    and Hash Table approach.\n\n---\n\n### Java - Counting (Clean Code)\n```\nclass Solution {\n    public int longestPalindrome(String[] words) {\n        int[][] counting = new int[26][26];\n        int max = 0;\n        for (String word : words) {\n            int a = word.charAt(0) - \'a\';\n            int b = word.charAt(1) - \'a\';\n            if (counting[b][a] > 0) {\n                max += 4;\n                counting[b][a]--;\n            } else {\n                counting[a][b]++;\n            }\n        }\n        for (int i = 0; i < 26; i++) {\n            if (counting[i][i] > 0) {\n                max += 2;\n                break;\n            }\n        }\n        return max;\n    }\n}\n```\n### Java - Counting (With Explanation)\n```\nclass Solution {\n    public int longestPalindrome(String[] words) {\n        // As there are only 2 lowercase English letters in each word, we can represent the word using a\n        // 2D array, with the row representing the first letter, and column representing the second letter.\n        int[][] counting = new int[26][26];\n        int max = 0;\n        for (String word : words) {\n            // Convert the char to its relative integer by subtracting with \'a\' (e.g. \'a\' == 0, \'b\' == 1, etc).\n            int a = word.charAt(0) - \'a\';\n            int b = word.charAt(1) - \'a\';\n            // We can flip the letters by using counting[b][a], while counting[a][b] represents the original lettering.\n            // If we found the pair corresponding to the flipped word, then we can increase the max by 4 and update\n            // the frequency of the flipped word.\n            // For Example: If "ab" is previously stored in counting[0][1], when the word "ba" came up later,\n            //              the flipped word of "ba" which is "ab" in counting[0][1] is found.\n            // This is also why it is a greedy algorithm, as we count pair in the final result as soon as it is found,\n            // since the position of the pair in a palindrome is not important, as long as they are placed opposite of\n            // each other.\n            if (counting[b][a] > 0) {\n                max += 4;\n                counting[b][a]--;\n            }\n            // If no pair is found, store the occurrence of the word.\n            else {\n                counting[a][b]++;\n            }\n        }\n        // For the odd word in the center of the palindrome (e.g. "aa", "bb", "cc", etc.),\n        // Check for all 26 possible pairs, if any is found, increase the max by 2.\n        // For Example: words = ["ab","ba","zz","yy"]\n        //              With "ab" and "ba" form a pair, with max = 4,\n        //              either "zz" or "yy" can fit in the center to expand the palindrome, forming "abzzba" or "abyyba".\n        // Do note that the valid pairs formed previously is already counted, since a == b, counting[a][b] == counting[b][a].\n        for (int i = 0; i < 26; i++) {\n            if (counting[i][i] > 0) {\n                max += 2;\n                break;\n            }\n        }\n        return max;\n    }\n}\n```\n---\n\n### Java - Hash Table (Clean Code)\n```\nclass Solution {\n    public int longestPalindrome(String[] words) {\n        Map<String, Integer> map = new HashMap<>();\n        int max = 0;\n        for (String word : words) {\n            String flipped = "" + word.charAt(1) + word.charAt(0);\n            if (map.containsKey(flipped)) {\n                max += 4;\n                map.put(flipped, map.get(flipped) - 1);\n                if (map.get(flipped) == 0) map.remove(flipped);\n            } else {\n                map.put(word, map.getOrDefault(word, 0) + 1);\n            }\n        }\n        for (int i = 0; i < 26; i++) {\n            char current = (char) (\'a\' + i);\n            if (map.getOrDefault("" + current + current, 0) > 0) {\n                max += 2;\n                break;\n            }\n        }\n        return max;\n    }\n}\n```\n\n### Java - Hash Table (With Explanation)\n\n```\nclass Solution {\n    public int longestPalindrome(String[] words) {\n        Map<String, Integer> map = new HashMap<>();\n        int max = 0;\n        for (String word : words) {\n            // Get the flipped word.\n            String flipped = "" + word.charAt(1) + word.charAt(0);\n\n            // If the flipped word is found, reduce the count of the flipped word.\n            // Removing the key from the map when it is 0 is important later on when we need to check for the center word\n            // that can form the palindrome.\n            if (map.containsKey(flipped)) {\n                max += 4;\n                map.put(flipped, map.get(flipped) - 1);\n                if (map.get(flipped) == 0) map.remove(flipped);\n            } else {\n                map.put(word, map.getOrDefault(word, 0) + 1);\n            }\n        }\n        // For the odd word in the center of the palindrome (e.g. "aa", "bb", "cc", etc.),\n        // Check for all 26 possible pairs, if any is found, increase the max by 2.\n        // For Example: words = ["ab","ba","zz","yy"]\n        //              With "ab" and "ba" form a pair, with max = 4,\n        //              either "zz" or "yy" can fit in the center to expand the palindrome, forming "abzzba" or "abyyba".\n        // Exit the for-loop once found, as we only can use one at the center.\n        for (int i = 0; i < 26; i++) {\n            char current = (char) (\'a\' + i);\n            if (map.getOrDefault("" + current + current, 0) > 0) {\n                max += 2;\n                break;\n            }\n        }\n        return max;\n    }\n}\n```
['Hash Table', 'Greedy', 'Counting', 'Java']