Longest Palindrome

Published: Nov 3, 2022

Easy Hash Table Counting Greedy String


This type of palindrome problems are there. Like Longest Palindrome by Concatenating Two Letter Words, not always, the palindrome string can be created. Often, multiple palindromes can be created. Start from counting the characters or words. Then, check each character whether the count is even or odd. Count those to meet with the requirements, then we can get the answer.

Problem Description

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.

Letters are case sensitive, for example, “Aa” is not considered a palindrome here.


  • 1 <= s.length <= 2000
  • s consists of lowercase and/or uppercase English letters only.



Example 1
Input: s = "abccccdd"
Output: 7
Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7.
Example 2
Input: s = "a"
Output: 1
Explanation: The longest palindrome that can be built is "a", whose length is 1.


In this case, the characters are given. Start from counting each character. Then, go over the count table. If the character’s count is even, add the count to the result. If the character’s count is odd, one forms a center element. Add count - 1 to the result. In the end, if the center element is found, add 1. This way, we can find the answer.


class LongestPalindrome:
    def longestPalindrome(self, s: str) -> int:
        counts = collections.Counter(s)
        result = 0
        center = False
        for _, cnt in counts.items():
            if cnt % 2 == 0:
                result += cnt
                result += cnt - 1
                center = True
        if center:
            result += 1
        return result


  • Time: O(n)
  • Space: O(1) – characters are only lower and/or upper case english letters, 52 at most which is constant