LeetCode: Longest Palindrome by Concatenating Two Letter Words Solution
Things get messy sometimesApproach
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, ba23ab: 2 times4ba: 4 times56We could only concatenate at maximum of 2 pairs78ab-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 dd23aa: 3 times4bb: 2 times5cc: 1 times6dd: 4 times78dd-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 )67 let res = 08 let occurencesOfSame = []910 for (const word of mapOccurences.keys()) {11 const reversedWord = word[1] + word[0]12 const isSame = word === reversedWord13 const occurence = mapOccurences.get(reversedWord)1415 if (!occurence) continue1617 if (isSame) {18 occurencesOfSame.push(occurence)19 } else {20 res +=21 Math.min(mapOccurences.get(word), mapOccurences.get(reversedWord)) * 422 }2324 mapOccurences.set(word, 0)25 mapOccurences.set(reversedWord, 0)26 }2728 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 }3839 res += (!oddOccurenceProcessed ? 2 : 0) + (occurencesOfSame[i] - 1) * 240 oddOccurenceProcessed = true41 }4243 return res44}
References
Similar problems
Palindrome Pairs
Comments
Loading comments...
Tags
leetcode
array
hash table
string
greedy
Apply and earn a $2,500 bonus once you're hired on your first job!
Clients from the Fortune 500 to Silicon Valley startups
Choose your own rate, get paid on time
From hourly, part-time, to full-time positions
Flexible remote working environment
A lot of open JavaScript jobs!!
Fact corner: Referred talent are 5x more likely to pass the Toptal screening process than the average applicant.
Still hesitate? Read HoningJS author's guide on dealing with Toptal interview process.