LeetCode: Longest Palindrome by Concatenating Two Letter Words Solution

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

1ba, ab, ba, ab, ba, ba
2
3ab: 2 times
4ba: 4 times
5
6We could only concatenate at maximum of 2 pairs
7
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 dd
2
3aa: 3 times
4bb: 2 times
5cc: 1 times
6dd: 4 times
7
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 = 0
8  let occurencesOfSame = []
9
10  for (const word of mapOccurences.keys()) {
11    const reversedWord = word[1] + word[0]
12    const isSame = word === reversedWord
13    const occurence = mapOccurences.get(reversedWord)
14
15    if (!occurence) continue
16
17    if (isSame) {
18      occurencesOfSame.push(occurence)
19    } else {
20      res +=
21        Math.min(mapOccurences.get(word), mapOccurences.get(reversedWord)) * 4
22    }
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] * 2
36      continue
37    }
38
39    res += (!oddOccurenceProcessed ? 2 : 0) + (occurencesOfSame[i] - 1) * 2
40    oddOccurenceProcessed = true
41  }
42
43  return res
44}

References

Original problem

Similar problems

Palindrome Pairs

Longest Palindrome