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)

SpaceComplexity: O(1)

""" 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()

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)

SpaceComplexity: O(1)

""" 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()

0409 - Longest Palindrome

Solution 1 - Greedy with Character Counting

Solution 2 - Greedy with Running Pair Count