Devin's Blog

Longest Palindrome by Concatenating Two Letter Words

3 min read

TARGET DECK: Leetcode FILE TAGS:

Intuition

  • If a word (2 letter string) equals its reverse, then count how many times that word and its reverse occurs, minus the difference between the two.
    • This is because you can have more of a word that has a reverse
      • ex) lc, cl, cl
  • This works since every word, if it has a reverse, can be combined
    • ex) lccl
  • For words that do not equal their reverse (so they are palindromes themselves) i.e. aa:
    • If there is an even number of that word, then that word is guaranteed to fit into any palindrome.
      • ex) aaaa can always fit into a preexisting palindrome, for example blaaaalb
    • If there is an odd number of that word, then we want to an include a maximally even amount of that odd number, so count[word] - 1.
      • However, the edge case is that one central word is allowed from the entire palindrome
        • ex) bb, ab, bb, ba, bb
      • Therefore, save the fact that you saw at least one odd numbered length 2 duplicate count, and add 1 to the result if indeed you saw such a count.

Cards

START Basic Front: Longest Palindrome by Concatenating Two Letter Words - LeetCode Back: Split cases of duplicate 2-letter word and non-duplicate, keeping in mind the central word (of which there can be only one duplicate 2-letter central word) for an odd count.

END

Complexity

Runtime

where N is the number of words.

Space

to save the counter of every word.

Code

Combined For Loops

class Solution:
    def longestPalindrome(self, words: List[str]) -> int:
        # Find words with no duplicates
        res = 0
        central = False
        counter = Counter(words)
        for word in words:
            rev = word[::-1]
            if word != rev:
                res += counter[word] + counter[rev] - abs(counter[word] - counter[rev])
                counter[word] = 0
                counter[rev] = 0
            else:
                if counter[word] % 2 == 0:
                    res += counter[word]
                else:
                    central = True
                    res += counter[word] - 1
                counter[word] = 0
 
        if central:
            res += 1
        return res * 2

Split

class Solution:
    def longestPalindrome(self, words: List[str]) -> int:
        # Find words with no duplicates
        res = 0
        counter = Counter(words)
        for word in words:
            rev = word[::-1]
            if word != rev:
                res += counter[word] + counter[rev] - abs(counter[word] - counter[rev])
                counter[word] = 0
                counter[rev] = 0
 
        central = False
        for word in words:
            rev = word[::-1]
            if word == rev:
                if counter[word] % 2 == 0:
                    res += counter[word]
                else:
                    central = True
                    res += counter[word] - 1
                counter[word] = 0
 
        if central:
            res += 1
        return res * 2

Notes

References

https://leetcode.com/problems/longest-palindrome-by-concatenating-two-letter-words/

Graph View