Simple java solution with explaination in o(n) space and time
We will try to decode algorithm and optimize it step by step.\n\n1. By looking at problem we know that we want to maximize length and it is possible by includin
We will try to decode algorithm and optimize it step by step.\n\n1. By looking at problem we know that we want to maximize length and it is possible by including as much as pairs as possible.\n2. To store the count of each pair we can take hashMap<String,Integer> where key will be word and value will be it\'s count. and similarly we take pair variable to count the total no of matching palindrome pair found so far.\n3. iterate word by word and check if map contains reverse of the string. if yes decrement count and update map. else if not present put original word to map and increment count by 1 (why increment? for below example cases).\n\nNow, why not hashset? \nbecause of cases like below ->\n["ab","ab","ab","ba","ba]\nif we take set we will not have ab count as 3, we will only know that ab exists. so when matching "ba" comes, in such case we will remove pair from set and update pair var. but now when next ba comes, pair count will remain same, as we dont know that know frequency. so we need frequency also.\n\nSo, are we done with the algo? no, why? becuase we need to handle case where word itself is palindrome. i.e. like "aa". in such case it will increase total of our answer by 2. \nBut will it always increase answer by 2? No,\n\nExample ->\n["aa","bc","aa"]\nhere both aa will form match and answer will be 4.\n\nand for cases like ->\n["aa","bc","cb","dd","dd","dd"]\nhere bc and cb will be pair.\ntwo dd will be pair\nand 1 of either aa or dd can also be part of answer.\nso total=10\n\nfor case ->\n["oo", "aa", "bb", "aa"]\nanswer will be 6.\n\nSo, we need one more variable "sym" which will count the symmetric words. we will decrement it when word is present in map already (i.e. reverse already exists). and increment it when not present. why? because for last example sym will be 3 till "bb". and when last element i.e. "aa" comes it will become 2.\nif we have used sym as boolean instead. we will set it to false after last "aa" found. and after loop finishes we dont know if we have one word which can be combined with "aaaa" to make say "aabbaa"\n```\n public int longestPalindrome(String[] words) {\n        //hold word,frequency of word\n        Map<String,Integer> map = new HashMap<>();\n        //total no of matching palindrome pairs exists\n        int pair=0;\n        //sym to hold count of symmetric word like "bb"\n        int sym=0;\n        //iterate word by word\n        for(String w:words) {\n            String rev = w.charAt(1)+""+w.charAt(0);\n            //we need to handle to case.\n            //1. reverse word occurred first time. in such case map will be empty for that word.\n            //2. matching pair has been found already.so word will be present already but with count 0. ex-< ["ab","ba","ab"]>\n            if(map.getOrDefault(rev,0)>0) {\n                //update pair\n                pair++;\n                //decrement count\n                map.put(rev,map.getOrDefault(rev,0)-1);\n                //check if it was symmetric word\n                if(rev.equals(w)) {\n                    sym--;\n                }\n            } else {\n                //if reverse not present. add original word and update count by 1. ex->["ab","ab","ab"]\n                map.put(w,map.getOrDefault(w,0)+1);\n                //for symmetry increase counter\n                if(rev.equals(w)) {\n                    sym++;\n                }\n            }\n        }\n        // pair * 4 and add if sym word count is not zero.\n        return pair*4+(sym!=0?2:0);\n    }\n```
['Hash Table', 'Greedy', 'Java']