409-LongestPalindrome

Longest Palindrome

Easy

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.

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.

Constraints:

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

Problem can be found in here!

Solution

Solution1: Hash Table

def longestPalindrome(s: str) -> int:
    memo = {}
    for token in s:
        try:
            memo[token] += 1
        except KeyError:
            memo[token] = 1

    longest_length = 0
    odd_flag = False
    for i in memo.values():
        if i % 2 == 0:
            longest_length += i
        else:
            odd_flag = True
            longest_length += (i-1)

    return longest_length + 1 if odd_flag else longest_length

Time Complexity: $O(n)$, Space Complexity: $O(n)$

Solution2: Set

def longestPalindrome(s: str) -> int:
    memo = set()
    for token in s:
        try:
            memo.remove(token)
        except KeyError:
            memo.add(token)

    has_odd_number = len(memo) > 0
    return len(s) - len(memo) + 1 if has_odd_number else len(s)

Time Complexity: $O(n)$, Space Complexity: $O(n)$