409. Longest Palindrome - Explanation

1. Hash Map

class Solution:
    def longestPalindrome(self, s: str) -> int:
        count = defaultdict(int)
        res = 0

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

        for cnt in count.values():
            if cnt % 2:
                res += 1
                break

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(m)$

Where $n$ is the length of the given string, and $m$ is the number of distinct characters in the string.

2. Hash Map (Optimal)

class Solution:
    def longestPalindrome(self, s: str) -> int:
        count = defaultdict(int)
        res = 0

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

        return res + (res < len(s))

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(m)$

Where $n$ is the length of the given string, and $m$ is the number of distinct characters in the string.

3. Hash Set

class Solution:
    def longestPalindrome(self, s: str) -> int:
        seen = set()
        res = 0

        for c in s:
            if c in seen:
                seen.remove(c)
                res += 2
            else:
                seen.add(c)

        return res + 1 if seen else res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(m)$

Where $n$ is the length of the given string, and $m$ is the number of distinct characters in the string.

4. Bitmask

class Solution:
    def longestPalindrome(self, s: str) -> int:
        mask1 = 0  # [a - z]
        mask2 = 0  # [A - Z]
        res = 0

        for c in s:
            if 'a' <= c <= 'z':
                bit = 1 << (ord(c) - ord('a'))
                if mask1 & bit:
                    res += 2
                mask1 ^= bit
            else:
                bit = 1 << (ord(c) - ord('A'))
                if mask2 & bit:
                    res += 2
                mask2 ^= bit

        return res + 1 if mask1 or mask2 else res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$