409. Longest Palindrome - Explanation

Description

You are 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 <= 2,000
s consists of lowercase and/or uppercase English letters only.

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Hash Maps / Hash Sets - Counting character frequencies or tracking characters with odd counts
Palindrome Properties - Understanding that palindromes require character pairs (even counts) with at most one odd-count character in the middle
Bit Manipulation (Optional) - Using bitmasks to track odd/even character counts for a space-optimized solution

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

Use a hash map to count each character's frequency.
Initialize result to 0.
For each character encountered, increment its count. When the count becomes even, add 2 to the result (a new pair formed).
After processing, check if any character has an odd count. If so, add 1 for the middle position.
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

public class Solution {
    public int longestPalindrome(String s) {
        Map<Character, Integer> count = new HashMap<>();
        int res = 0;

        for (char c : s.toCharArray()) {
            count.put(c, count.getOrDefault(c, 0) + 1);
            if (count.get(c) % 2 == 0) {
                res += 2;
            }
        }

        for (int cnt : count.values()) {
            if (cnt % 2 == 1) {
                res += 1;
                break;
            }
        }

        return res;
    }
}

class Solution {
public:
    int longestPalindrome(string s) {
        unordered_map<char, int> count;
        int res = 0;

        for (char c : s) {
            count[c]++;
            if (count[c] % 2 == 0) {
                res += 2;
            }
        }

        for (auto& [ch, cnt] : count) {
            if (cnt % 2 == 1) {
                res += 1;
                break;
            }
        }

        return res;
    }
};

class Solution {
    /**
     * @param {string} s
     * @return {number}
     */
    longestPalindrome(s) {
        const count = {};
        let res = 0;

        for (let c of s) {
            count[c] = (count[c] || 0) + 1;
            if (count[c] % 2 === 0) {
                res += 2;
            }
        }

        for (let key in count) {
            if (count[key] % 2 === 1) {
                res += 1;
                break;
            }
        }

        return res;
    }
}

public class Solution {
    public int LongestPalindrome(string s) {
        var count = new Dictionary<char, int>();
        int res = 0;

        foreach (char c in s) {
            if (!count.ContainsKey(c)) {
                count[c] = 0;
            }
            count[c]++;
            if (count[c] % 2 == 0) {
                res += 2;
            }
        }

        foreach (int cnt in count.Values) {
            if (cnt % 2 == 1) {
                res += 1;
                break;
            }
        }

        return res;
    }
}

func longestPalindrome(s string) int {
    count := make(map[rune]int)
    res := 0

    for _, c := range s {
        count[c]++
        if count[c]%2 == 0 {
            res += 2
        }
    }

    for _, cnt := range count {
        if cnt%2 == 1 {
            res++
            break
        }
    }

    return res
}

class Solution {
    fun longestPalindrome(s: String): Int {
        val count = mutableMapOf<Char, Int>()
        var res = 0

        for (c in s) {
            count[c] = count.getOrDefault(c, 0) + 1
            if (count[c]!! % 2 == 0) {
                res += 2
            }
        }

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

        return res
    }
}

class Solution {
    func longestPalindrome(_ s: String) -> Int {
        var count = [Character: Int]()
        var res = 0

        for c in s {
            count[c, default: 0] += 1
            if count[c]! % 2 == 0 {
                res += 2
            }
        }

        for cnt in count.values {
            if cnt % 2 == 1 {
                res += 1
                break
            }
        }

        return res
    }
}

class Solution {
    /**
     * @param {string} s
     * @return {number}
     */
    longestPalindrome(s: string): number {
        const count: Record<string, number> = {};
        let res = 0;

        for (const c of s) {
            count[c] = (count[c] || 0) + 1;
            if (count[c] % 2 === 0) {
                res += 2;
            }
        }

        for (const key in count) {
            if (count[key] % 2 === 1) {
                res += 1;
                break;
            }
        }

        return res;
    }
}

impl Solution {
    pub fn longest_palindrome(s: String) -> i32 {
        let mut count = HashMap::new();
        let mut res = 0;

        for c in s.chars() {
            let e = count.entry(c).or_insert(0);
            *e += 1;
            if *e % 2 == 0 {
                res += 2;
            }
        }

        for &cnt in count.values() {
            if cnt % 2 == 1 {
                res += 1;
                break;
            }
        }

        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

Count characters and accumulate pairs as before.
After counting, if result < length of string, add 1 (there's a leftover character for the middle).
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))

public class Solution {
    public int longestPalindrome(String s) {
        Map<Character, Integer> count = new HashMap<>();
        int res = 0;

        for (char c : s.toCharArray()) {
            count.put(c, count.getOrDefault(c, 0) + 1);
            if (count.get(c) % 2 == 0) {
                res += 2;
            }
        }

        return res + (res < s.length() ? 1 : 0);
    }
}

class Solution {
public:
    int longestPalindrome(string s) {
        unordered_map<char, int> count;
        int res = 0;

        for (char c : s) {
            count[c]++;
            if (count[c] % 2 == 0) {
                res += 2;
            }
        }

        return res + (res < s.size());
    }
};

class Solution {
    /**
     * @param {string} s
     * @return {number}
     */
    longestPalindrome(s) {
        const count = {};
        let res = 0;

        for (let c of s) {
            count[c] = (count[c] || 0) + 1;
            if (count[c] % 2 === 0) {
                res += 2;
            }
        }

        return res + (res < s.length ? 1 : 0);
    }
}

public class Solution {
    public int LongestPalindrome(string s) {
        var count = new Dictionary<char, int>();
        int res = 0;

        foreach (char c in s) {
            if (!count.ContainsKey(c)) {
                count[c] = 0;
            }
            count[c]++;
            if (count[c] % 2 == 0) {
                res += 2;
            }
        }

        return res + (res < s.Length ? 1 : 0);
    }
}

func longestPalindrome(s string) int {
    count := make(map[rune]int)
    res := 0

    for _, c := range s {
        count[c]++
        if count[c]%2 == 0 {
            res += 2
        }
    }

    if res < len(s) {
        return res + 1
    }
    return res
}

class Solution {
    fun longestPalindrome(s: String): Int {
        val count = mutableMapOf<Char, Int>()
        var res = 0

        for (c in s) {
            count[c] = count.getOrDefault(c, 0) + 1
            if (count[c]!! % 2 == 0) {
                res += 2
            }
        }

        return res + if (res < s.length) 1 else 0
    }
}

class Solution {
    func longestPalindrome(_ s: String) -> Int {
        var count = [Character: Int]()
        var res = 0

        for c in s {
            count[c, default: 0] += 1
            if count[c]! % 2 == 0 {
                res += 2
            }
        }

        return res + (res < s.count ? 1 : 0)
    }
}

class Solution {
    /**
     * @param {string} s
     * @return {number}
     */
    longestPalindrome(s: string): number {
        const count: Record<string, number> = {};
        let res = 0;
        for (const c of s) {
            count[c] = (count[c] || 0) + 1;
            if (count[c] % 2 === 0) {
                res += 2;
            }
        }
        return res + (res < s.length ? 1 : 0);
    }
}

impl Solution {
    pub fn longest_palindrome(s: String) -> i32 {
        let mut count = HashMap::new();
        let mut res = 0i32;

        for c in s.chars() {
            let e = count.entry(c).or_insert(0);
            *e += 1;
            if *e % 2 == 0 {
                res += 2;
            }
        }

        if res < s.len() as i32 { res + 1 } 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.

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

Initialize an empty set and result to 0.
For each character:
- If it's in the set, remove it and add 2 to result (pair completed).
- Otherwise, add it to the set.
If the set is non-empty after processing, add 1 to result.
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

public class Solution {
    public int longestPalindrome(String s) {
        Set<Character> seen = new HashSet<>();
        int res = 0;

        for (char c : s.toCharArray()) {
            if (seen.contains(c)) {
                seen.remove(c);
                res += 2;
            } else {
                seen.add(c);
            }
        }

        return seen.isEmpty() ? res : res + 1;
    }
}

class Solution {
public:
    int longestPalindrome(string s) {
        unordered_set<char> seen;
        int res = 0;

        for (char c : s) {
            if (seen.count(c)) {
                seen.erase(c);
                res += 2;
            } else {
                seen.insert(c);
            }
        }

        return seen.empty() ? res : res + 1;
    }
};

class Solution {
    /**
     * @param {string} s
     * @return {number}
     */
    longestPalindrome(s) {
        const seen = new Set();
        let res = 0;

        for (let c of s) {
            if (seen.has(c)) {
                seen.delete(c);
                res += 2;
            } else {
                seen.add(c);
            }
        }

        return seen.size === 0 ? res : res + 1;
    }
}

public class Solution {
    public int LongestPalindrome(string s) {
        var seen = new HashSet<char>();
        int res = 0;

        foreach (char c in s) {
            if (seen.Contains(c)) {
                seen.Remove(c);
                res += 2;
            } else {
                seen.Add(c);
            }
        }

        return seen.Count == 0 ? res : res + 1;
    }
}

func longestPalindrome(s string) int {
    seen := make(map[rune]bool)
    res := 0

    for _, c := range s {
        if seen[c] {
            delete(seen, c)
            res += 2
        } else {
            seen[c] = true
        }
    }

    if len(seen) == 0 {
        return res
    }
    return res + 1
}

class Solution {
    fun longestPalindrome(s: String): Int {
        val seen = mutableSetOf<Char>()
        var res = 0

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

        return if (seen.isEmpty()) res else res + 1
    }
}

class Solution {
    func longestPalindrome(_ s: String) -> Int {
        var seen = Set<Character>()
        var res = 0

        for c in s {
            if seen.contains(c) {
                seen.remove(c)
                res += 2
            } else {
                seen.insert(c)
            }
        }

        return seen.isEmpty ? res : res + 1
    }
}

class Solution {
    /**
     * @param {string} s
     * @return {number}
     */
    longestPalindrome(s: string): number {
        const seen = new Set<string>();
        let res = 0;
        for (const c of s) {
            if (seen.has(c)) {
                seen.delete(c);
                res += 2;
            } else {
                seen.add(c);
            }
        }
        return seen.size === 0 ? res : res + 1;
    }
}

impl Solution {
    pub fn longest_palindrome(s: String) -> i32 {
        let mut seen = HashSet::new();
        let mut res = 0;

        for c in s.chars() {
            if seen.contains(&c) {
                seen.remove(&c);
                res += 2;
            } else {
                seen.insert(c);
            }
        }

        if seen.is_empty() { res } else { res + 1 }
    }
}

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

Use two bitmasks: one for lowercase (a-z), one for uppercase (A-Z).
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.
If either mask is non-zero at the end, add 1 for the middle.
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

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

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

        return (mask1 != 0 || mask2 != 0) ? res + 1 : 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;
    }
};

class Solution {
    /**
     * @param {string} s
     * @return {number}
     */
    longestPalindrome(s) {
        let mask1 = 0; // [a - z]
        let mask2 = 0; // [A - Z]
        let res = 0;

        for (let c of s) {
            if (c >= 'a' && c <= 'z') {
                let bit = 1 << (c.charCodeAt(0) - 97);
                if (mask1 & bit) {
                    res += 2;
                }
                mask1 ^= bit;
            } else {
                let bit = 1 << (c.charCodeAt(0) - 65);
                if (mask2 & bit) {
                    res += 2;
                }
                mask2 ^= bit;
            }
        }

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

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

        foreach (char c in s) {
            if (c >= 'a' && c <= 'z') {
                int bit = 1 << (c - 'a');
                if ((mask1 & bit) != 0) {
                    res += 2;
                }
                mask1 ^= bit;
            } else {
                int bit = 1 << (c - 'A');
                if ((mask2 & bit) != 0) {
                    res += 2;
                }
                mask2 ^= bit;
            }
        }

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

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

    for _, c := range s {
        if c >= 'a' && c <= 'z' {
            bit := 1 << (c - 'a')
            if mask1&bit != 0 {
                res += 2
            }
            mask1 ^= bit
        } else {
            bit := 1 << (c - 'A')
            if mask2&bit != 0 {
                res += 2
            }
            mask2 ^= bit
        }
    }

    if mask1 != 0 || mask2 != 0 {
        return res + 1
    }
    return res
}

class Solution {
    fun longestPalindrome(s: String): Int {
        var mask1 = 0 // [a - z]
        var mask2 = 0 // [A - Z]
        var res = 0

        for (c in s) {
            if (c in 'a'..'z') {
                val bit = 1 shl (c - 'a')
                if (mask1 and bit != 0) {
                    res += 2
                }
                mask1 = mask1 xor bit
            } else {
                val bit = 1 shl (c - 'A')
                if (mask2 and bit != 0) {
                    res += 2
                }
                mask2 = mask2 xor bit
            }
        }

        return if (mask1 != 0 || mask2 != 0) res + 1 else res
    }
}

class Solution {
    func longestPalindrome(_ s: String) -> Int {
        var mask1 = 0 // [a - z]
        var mask2 = 0 // [A - Z]
        var res = 0

        for c in s {
            let asciiValue = Int(c.asciiValue!)
            if c >= "a" && c <= "z" {
                let bit = 1 << (asciiValue - 97)
                if mask1 & bit != 0 {
                    res += 2
                }
                mask1 ^= bit
            } else {
                let bit = 1 << (asciiValue - 65)
                if mask2 & bit != 0 {
                    res += 2
                }
                mask2 ^= bit
            }
        }

        return (mask1 != 0 || mask2 != 0) ? res + 1 : res
    }
}

class Solution {
    /**
     * @param {string} s
     * @return {number}
     */
    longestPalindrome(s: string): number {
        let mask1 = 0; // [a - z]
        let mask2 = 0; // [A - Z]
        let res = 0;
        for (const c of s) {
            if (c >= 'a' && c <= 'z') {
                const bit = 1 << (c.charCodeAt(0) - 97);
                if (mask1 & bit) {
                    res += 2;
                }
                mask1 ^= bit;
            } else {
                const bit = 1 << (c.charCodeAt(0) - 65);
                if (mask2 & bit) {
                    res += 2;
                }
                mask2 ^= bit;
            }
        }
        return mask1 || mask2 ? res + 1 : res;
    }
}

impl Solution {
    pub fn longest_palindrome(s: String) -> i32 {
        let mut mask1: u32 = 0; // [a - z]
        let mut mask2: u32 = 0; // [A - Z]
        let mut res = 0;

        for c in s.bytes() {
            if c >= b'a' && c <= b'z' {
                let bit = 1u32 << (c - b'a');
                if mask1 & bit != 0 {
                    res += 2;
                }
                mask1 ^= bit;
            } else {
                let bit = 1u32 << (c - b'A');
                if mask2 & bit != 0 {
                    res += 2;
                }
                mask2 ^= bit;
            }
        }

        if mask1 != 0 || mask2 != 0 { res + 1 } 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.