409. Longest Palindrome - Explanation

Problem Link

1. Hash Map

Intuition

A palindrome reads the same forwards and backwards. For most characters, we need pairs: one for each side. Characters with even counts can be fully used. Characters with odd counts contribute their largest even portion, and at most one odd character can sit in the middle. We count character frequencies and sum up pairs as we find them.

Algorithm

1. Use a hash map to count each character's frequency.
2. Initialize result to 0.
3. For each character encountered, increment its count. When the count becomes even, add 2 to the result (a new pair formed).
4. After processing, check if any character has an odd count. If so, add 1 for the middle position.
5. Return the result.

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)

Intuition

We can simplify the check for the middle character. If the total count of paired characters is less than the string length, it means at least one character has an odd count, so we can place one in the middle. This eliminates the need for a separate loop to check for odd counts.

Algorithm

1. Count characters and accumulate pairs as before.
2. After counting, if result < length of string, add 1 (there's a leftover character for the middle).
3. Return the result.

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

Intuition

Instead of counting exact frequencies, we only need to know if a character has been seen an odd number of times. A set works perfectly: add a character when first seen, remove it when seen again (forming a pair). Each removal represents a pair. At the end, if the set is non-empty, we can use one character as the center.

Algorithm

1. Initialize an empty set and result to 0.
2. For each character:
   • If it's in the set, remove it and add 2 to result (pair completed).
   • Otherwise, add it to the set.
3. If the set is non-empty after processing, add 1 to result.
4. Return the result.

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

Intuition

Since we're only dealing with lowercase and uppercase English letters (52 total), we can use two 32-bit integers as bitmasks instead of a set. Each bit represents whether that character has been seen an odd number of times. Toggling a bit (XOR) when we see a character tracks odd/even status. When a bit flips from 1 to 0, we found a pair.

Algorithm

1. Use two bitmasks: one for lowercase (a-z), one for uppercase (A-Z).
2. For each character:
   • Compute the bit position based on its ASCII value.
   • If the bit is set (odd count), add 2 to result (pair formed).
   • Toggle the bit with XOR.
3. If either mask is non-zero at the end, add 1 for the middle.
4. Return the result.

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)$

---

Common Pitfalls

Forgetting the Middle Character

A common mistake is forgetting that a palindrome can have one character with an odd count placed in the center. After counting all pairs, you must check if any character has a leftover (odd count) and add 1 to the result if so. Without this, you will undercount the length for strings like "abcba" where "c" can be the center.

Case Sensitivity

The problem distinguishes between uppercase and lowercase letters ('A' and 'a' are different characters). A frequent error is treating them as the same character or forgetting to handle both cases. Make sure your counting logic accounts for the full character set specified in the problem constraints.