409. Longest Palindrome

At a Glance

• Topic: String
• Pattern: Hash Map
• Difficulty: Easy
• LeetCode: 409

Problem Statement

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.

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.

Approach & Solution Steps

Use a hash set to track characters with odd frequencies. If a character is already in the set, it forms a pair, so remove it and add 2 to the length. Finally, add 1 to the length if the set is not empty (for a central character).

Optimal JS Solution

function longestPalindrome(s) {
  const set = new Set();
  let length = 0;
  for (const char of s) {
    if (set.has(char)) {
      length += 2;
      set.delete(char);
    } else {
      set.add(char);
    }
  }
  return set.size > 0 ? length + 1 : length;
}

Edge Cases & Pitfalls

• Always consider empty or null inputs.
• Watch out for off-by-one index errors.