Logo
    Akhil Abraham
    Akhil Abraham
    0409 - Longest Palindrome
    0409 - Longest Palindrome

    0409 - Longest Palindrome

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/longest-palindrome/

    Solution 1 - Greedy with Character Counting

    Count the frequency of each character. For each character, add the largest even portion of its count to the result. If any character has an odd count, we can place one in the center, so add 1 at the end if the result is less than the string length.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)

    Solution 2 - Greedy with Running Pair Count

    Instead of counting all characters first and then processing, accumulate pairs on the fly. For each character, increment its count. Whenever a count becomes even, add 2 to the result. At the end, if the result is less than the string length, add 1 for a possible center character.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    """ 0409.1 - Longest Palindrome - Solution 1 - Greedy with Character Counting """

#####################################################################################
# Imports
#####################################################################################
from collections import Counter

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def longestPalindrome(self, s: str) -> int:
        """Longest Palindrome Function"""
        counts = Counter(s)
        result = 0

        for count in counts.values():
            result += count // 2 * 2

        if result < len(s):
            result += 1

        return result


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().longestPalindrome("abccccdd"))  # 7
    print(Solution().longestPalindrome("a"))          # 1
    print(Solution().longestPalindrome("Aa"))         # 1


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

    """ 0409.2 - Longest Palindrome - Solution 2 - Greedy with Running Pair Count """

#####################################################################################
# Imports
#####################################################################################
from collections import defaultdict

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def longestPalindrome(self, s: str) -> int:
        """Longest Palindrome Function"""
        count = defaultdict(int)
        res = 0

        for c in s:
            count[c] += 1
            if count[c] % 2 == 0:
                res += 2

        return res + (res < len(s))


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().longestPalindrome("abccccdd"))  # 7
    print(Solution().longestPalindrome("a"))          # 1
    print(Solution().longestPalindrome("Aa"))         # 1


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()