Longest Palindrome

How it works

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.

Steps

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.

Complexity

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

Things to watch for

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.

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

class Solution {
public:
    int longestPalindrome(string s) {
        int mask1 = 0; // [a - z]
        int mask2 = 0; // [A - Z]
        int res = 0;

        for (char c : s) {
            if ('a' <= c && c <= 'z') {
                int bit = 1 << (c - 'a');
                if (mask1 & bit) {
                    res += 2;
                }
                mask1 ^= bit;
            } else {
                int bit = 1 << (c - 'A');
                if (mask2 & bit) {
                    res += 2;
                }
                mask2 ^= bit;
            }
        }

        return (mask1 || mask2) ? res + 1 : res;
    }
};