A print shop builds palindromic badge codes from leftover letter stickers so a scanner reads the same both ways. The intern sorted the bag, glued matching pairs, and dumped leftover singles in the scrap bin. A handful of stickers made even-length badges instantly. A weekend run of mixed-case leftover stock produced codes one character short: one leftover sticker could have sat in the middle.

Longest Palindrome asks for the length of the longest palindrome you can build by rearranging the given letters. Each character may be used at most as often as it appears. This is not a window inside the original string. Valid Palindrome checks a phrase. Longest Palindromic Substring asks for a contiguous slice. Here you rearrange.

This is an interview writeup, not a hashing lecture. The hash table post owns buckets and collisions. Here we only care about letter frequencies so every even pair goes into the palindrome and at most one leftover odd sits in the center.

The problem

Given a string of uppercase and lowercase English letters, return the length of the longest palindrome you can build from those letters. You may rearrange freely. You may not invent extra copies of a letter.

s = "abccccdd"  →  7    one construction: dccaccd
s = "a"         →  1
s = "Aa"        →  1    'A' and 'a' are different

Note: Case is significant. "Aa" cannot become "Aa" as a palindrome of length 2. The contiguous slice "cccc" inside "abccccdd" is length 4; the built palindrome is 7. Do not recycle a substring proof.

Sort and pair, then throw the leftovers away

Copy to a char array, sort so equal letters sit together, walk adjacent equals as pairs, skip every leftover single. Correct for the even skeleton. Wrong as soon as any odd leftover could sit in the center.

int longestPalindromeEvenOnly(String s) {
    char[] a = s.toCharArray();
    Arrays.sort(a);
    int length = 0;
    int i = 0;
    while (i < a.length) {
        if (i + 1 < a.length && a[i] == a[i + 1]) {
            length += 2;
            i += 2;
        } else {
            i++;
        }
    }
    return length;
}

On "abccccdd" that walk returns 6. On "a" it returns 0. At a handful of stickers this looks fine. It is the even half of the answer, missing the one-character center: may one leftover odd sit in the middle?

Counts: every even pair, then at most one odd

Count each letter. For every frequency n, add n - (n % 2) — the largest even number of that letter. If any frequency was odd, add 1 for a center. You never permute the string. A 128-slot array covers ASCII letters; a map is the same idea when the alphabet is not a small table.

Walk "abccccdd":

s = "abccccdd"

counts:  a:1  b:1  c:4  d:2
even parts:  a:0  b:0  c:4  d:2    length = 6
any odd leftover? yes (a, and b)   +1 center
answer 7

The Java is that walk:

int longestPalindrome(String s) {
    int[] count = new int[128];
    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i)]++;
    }
    int length = 0;
    boolean odd = false;
    for (int n : count) {
        length += n - (n % 2);
        if (n % 2 == 1) {
            odd = true;
        }
    }
    if (odd) {
        length++;
    }
    return length;
}

Time is O(n) — one pass over the string, then a fixed scan of 128 slots. Space is O(1) for that table. A map would pay extra space if the follow-up opens Unicode; that layout is the hash-table post, not this board.

Note: Five cs still contribute four letters. An odd count is not a throwaway character. You take every even pair from every letter, then at most one leftover as the center. Two different odds still add only +1, not +2.

What interviewers usually poke next

  • Return the string, not the length. Emit n / 2 copies of each letter on the left, reverse them on the right, put one leftover odd in the middle. Length is this post; construction is the same counts.
  • All unique letters. Every count is 1. Answer is 1. The even-only brute returns 0.
  • Unicode, not just ASCII. The 128-slot array is a lie. Use a map, same even-parts-then-one-odd walk.
  • Cannot rearrange. That is a different prompt — substring or subsequence of the original. This count does not answer either.

You are done with this problem when you can say, out loud, why pairing after a sort is the even skeleton, why one leftover odd is legal in the center, and why this length is not the longest palindromic substring of the original string.