Longest Palindrome

easy string hash map greedy

Problem

Given a string s, find the length of the longest palindrome that can be built using the letters of s (each instance can be used at most once). Letters are case-sensitive.

Inputs = "abccccdd"

Output7

"dccaccd" is one such palindrome — use all pairs plus a single center letter.

def longest_palindrome(s):
    cnt = {}
    for c in s: cnt[c] = cnt.get(c, 0) + 1
    length, has_odd = 0, False
    for v in cnt.values():
        length += v // 2 * 2
        if v % 2 == 1: has_odd = True
    return length + (1 if has_odd else 0)

function longestPalindrome(s) {
  const cnt = {};
  for (const c of s) cnt[c] = (cnt[c] || 0) + 1;
  let length = 0, hasOdd = false;
  for (const v of Object.values(cnt)) {
    length += Math.floor(v / 2) * 2;
    if (v % 2 === 1) hasOdd = true;
  }
  return length + (hasOdd ? 1 : 0);
}

class Solution {
    public int longestPalindrome(String s) {
        int[] cnt = new int[128];
        for (char c : s.toCharArray()) cnt[c]++;
        int length = 0; boolean hasOdd = false;
        for (int v : cnt) {
            length += (v / 2) * 2;
            if (v % 2 == 1) hasOdd = true;
        }
        return length + (hasOdd ? 1 : 0);
    }
}

int longestPalindrome(string s) {
    int cnt[128] = {0};
    for (char c : s) cnt[(int)c]++;
    int length = 0; bool hasOdd = false;
    for (int v : cnt) {
        length += (v / 2) * 2;
        if (v % 2 == 1) hasOdd = true;
    }
    return length + (hasOdd ? 1 : 0);
}

Explanation

A palindrome is symmetric, so letters mostly come in matching pairs — one on each side. The only exception is a single center letter, which is allowed to stand alone. So we want to use as many pairs as possible, plus at most one odd letter in the middle.

We count how often each character appears. For a letter with count v, it can donate v // 2 * 2 letters as full pairs. For example a count of 5 gives 4 paired letters with 1 left over.

While summing pairs, we also watch whether any letter had an odd count. If so, exactly one leftover letter can be dropped into the center, adding +1 to the total — and we only ever add this bonus once.

Example: s = "abccccdd". Counts: a:1, b:1, c:4, d:2. Pairs give 0+0+4+2 = 6 letters, and since odd counts exist (a and b), we add one center letter for a total of 7.

Note this is case-sensitive, so 'A' and 'a' are treated as different characters. It's a single pass over the counts.

Time: O(n) Space: O(k) (alphabet size)