# LeetCode: Longest Palindrome by Concatenating Two Letter Words Solution

Things get messy sometimes

## Approach

Count the occurence of each word

Process 2 types of word separatedly

For normal words, count number of reverse words and sum up by taking the min occurence and multiply by 4

```.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}ba, ab, ba, ab, ba, ba2
3ab: 2 times4ba: 4 times5
6We could only concatenate at maximum of 2 pairs7
8ab-ab-ba-ba```

For palindrome words:

• if the word occurs even times, just multiply by 2
• if the word occurs odd times, take the max odd just for once and multiply by 2, and the rest minus 1 then turn to case of even times
```1aa aa aa bb bb cc dd dd dd dd2
3aa: 3 times4bb: 2 times5cc: 1 times6dd: 4 times7
8dd-dd-bb-aa-aa-aa-bb-dd-dd```

## Implementation

```1var longestPalindrome = function (words) {2  const mapOccurences = words.reduce(3    (acc, el) => acc.set(el, (acc.get(el) || 0) + 1),4    new Map()5  )6
7  let res = 08  let occurencesOfSame = []9
10  for (const word of mapOccurences.keys()) {11    const reversedWord = word[1] + word[0]12    const isSame = word === reversedWord13    const occurence = mapOccurences.get(reversedWord)14
15    if (!occurence) continue16
17    if (isSame) {18      occurencesOfSame.push(occurence)19    } else {20      res +=21        Math.min(mapOccurences.get(word), mapOccurences.get(reversedWord)) * 422    }23
24    mapOccurences.set(word, 0)25    mapOccurences.set(reversedWord, 0)26  }27
28  occurencesOfSame.sort((a, b) => b - a)29  for (30    let oddOccurenceProcessed = false, i = 0;31    i < occurencesOfSame.length;32    i++33  ) {34    if (occurencesOfSame[i] % 2 === 0) {35      res += occurencesOfSame[i] * 236      continue37    }38
39    res += (!oddOccurenceProcessed ? 2 : 0) + (occurencesOfSame[i] - 1) * 240    oddOccurenceProcessed = true41  }42
43  return res44}```

Original problem

## Similar problems

Palindrome Pairs

Longest Palindrome

leetcode

array

hash table

string

greedy

## Next Post

LeetCode: Invert Binary Tree

Sep 2, 2022

A Broken Interview: The Origin

## Previous Post

LeetCode: Sort List

Aug 29, 2022

Yeah I skipped the follow-up

Search Posts