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.

Note: You can use any characters from the string, and you can rearrange them arbitrarily.

Examples

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 is "a".

Example 3:

Input: s = "bb"
Output: 2
Explanation: The longest palindrome is "bb".

Constraints

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

Thinking Process

  1. Palindrome Structure: Symmetric pairs + optional center
  • Greedy works when local optimal choices lead to global optimum.
  • Often sort first to make the greedy choice obvious.
  • Prove or sanity-check: would swapping two choices ever help?
Greedy choice pick locally best after sorting

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Sort + greedy (this problem) O(n log n) O(1) Interval scheduling, assignment
Local greedy choice O(n) O(1) Jump game, gas station
Greedy + heap O(n log n) O(n) Merge streams, room allocation
Exchange argument O(n) O(1) Prove greedy choice is safe

Solution

class Solution {
public:
    int longestPalindrome(string s) {
        int maskl = 0; //[a - z]
        int maskU = 0; //[A - Z]
        int rtn = 0;
        for(char c: s) {
            if('a' <= c && c <= 'z') {
                int bit = 1 << (c - 'a');
                if(maskl & bit) {
                    rtn += 2;
                }
                maskl ^= bit;
            } else {
                int bit = 1 << (c - 'A');
                if(maskU & bit) {
                    rtn += 2;
                }
                maskU ^= bit;
            }
        }
        return (maskl || maskU) ? rtn + 1: rtn;
    }
};

Solution Explanation

Approach: Sort + greedy (this problem)

Key idea: 1. Palindrome Structure: Symmetric pairs + optional center

How the code works:

  1. Palindrome Structure: Symmetric pairs + optional center
    • Greedy works when local optimal choices lead to global optimum.
    • Often sort first to make the greedy choice obvious.
    • Prove or sanity-check: would swapping two choices ever help?

Walkthrough — input s = "abccccdd", expected output 7:

One longest palindrome that can be built is “dccaccd”, whose length is 7.

Common Mistakes

  1. Single character: s = "a" → return 1
  2. All pairs: s = "bb" → return 2
  3. All same character: s = "aaaa" → return 4
  4. Mixed case: s = "Aa" → return 1 (case sensitive)
  5. No pairs: s = "abc" → return 1 (one character in center)

  6. All unique: s = "abcdef" → return 1

  7. Case sensitivity: Treating ‘A’ and ‘a’ as same
  8. Center placement: Forgetting to add 1 when odd counts exist
  9. Pair counting: Incorrectly counting pairs
  10. Bit manipulation: Off-by-one errors in bit shifting
  11. Empty string: Not handling edge case (but constraints guarantee length ≥ 1)

Key Takeaways

  1. Palindrome Structure: Symmetric pairs + optional center
  2. Pair Counting: Each pair contributes 2 to length
  3. Odd Handling: At most one character can be in center
  4. Bit Manipulation: Efficient way to track odd/even counts
  5. Case Sensitivity: Must handle uppercase and lowercase separately

References

Template Reference