[Leetcode] 2131. Longest Palindrome by Concatenating Two Letter Words

https://leetcode.com/problems/longest-palindrome-by-concatenating-two-letter-words/description/?envType=daily-question&envId=2025-05-25

initial

my logic was wrong for takign care of the already palindromic string like aa or bb. I just took the longest already palindromic string like bbbb and added 4 to my already int variable. But if we have all already palindromic strings, this doesnt work cuz the length of longest pal string isnt the ans.

my initial logic

            if(key.equals(reversed)){
                already=Math.max(already,val*2);
            } 

correct, we need to take care of the middle part as well if its not filled and count is odd number

if(key.equals(reversed)){
                ans += (val/2)*4;
                if(!hasMiddle && val%2==1){
                    ans+=2;
                    hasMiddle=true;
                }

sol

we can either remove the keys and use concurrent hash map OR use .compareTo()

                    // Only process once (when word < reverse lexicographically)
                    if (word.compareTo(reverse) < 0) {
                        int reverseCount = map.get(reverse);
                        int pairs = Math.min(count, reverseCount);
                        ans += pairs * 4; // Each pair contributes 4 to length
                    }

so

class Solution {
    public int longestPalindrome(String[] words) {
        Map<String,Integer> map = new ConcurrentHashMap<>();
        for(String word: words){
            map.put(word,map.getOrDefault(word,0)+1);
        }
        int ans=0;
        boolean hasMiddle = false;
        for(Map.Entry<String,Integer> entry: map.entrySet()){
            String key = entry.getKey();
            int val = entry.getValue();

            StringBuilder sb = new StringBuilder(key);
            sb.reverse();
            String reversed = sb.toString();
            int reverseVal= map.getOrDefault(reversed,0);

            if(key.equals(reversed)){
                ans += (val/2)*4;
                if(!hasMiddle && val%2==1){
                    ans+=2;
                    hasMiddle=true;
                }
            } else{
                ans+=Math.min(val,reverseVal)*4;
                map.remove(key);
                map.remove(reversed);
            }
        }
        return ans;
    }
}

complexity

n where n is length of that words array
space is the key so worst case n