The O(n) Club: Longest Palindrome – How to Build One Without Breaking a Sweat

The O(n) Club: Longest Palindrome – How to Build One Without Breaking a Sweat

⚡ TL;DR

This isn’t “is it a palindrome?” country — it’s “how ridiculously big a palindrome can I build out of these poor, unsuspecting letters?” The secret sauce: use every pair you can, and if there’s a leftover singleton, slap it in the middle like a cherry on a sundae. Java in five lines:

// Build it, don't check it
public int longestPalindrome(String s) {
    int[] freq = new int[128];
    for (char c : s.toCharArray()) freq[c]++;
    int len = 0;
    for (int f : freq) len += (f / 2) * 2;
    if (len < s.length()) len++;
    return len;
}

🧠 How Devs Usually Mess This Up

Classic dev move: panic, reach for your palindrome checker, or (for those who like pain) try dynamic programming. Sorry—the job description is actually “maximum wall-mountable mirror symmetry using spare letter parts.” Order doesn’t matter. Pair ’em up, drop an oddball if you have one, and ignore your impulse to be clever with substrings.

🔍 What’s Actually Going On

Imagine being a chef at a symmetry-themed sandwich shop. Your job: for every letter slice, find its twin and stick them on either side. If you’re left with an awkward single slice at the end? Embrace the chaos and put it in the center. That’s your whole palindrome. No need for knuthian wisdom or recursive dreams—just counting and stacking sandwiches.

🛠️ PseudoCode

• Count each character’s frequency:

  for (char c : s.toCharArray()) freq[c]++;

  (Arrays are your sous chefs.)
• Sum every pair up:

  for (int f : freq) len += (f / 2) * 2;

  (Every pair goes straight to the sandwich ends.)
• If you didn’t use every character, one oddball gets the starring center role:

  if (len < s.length()) len++;

• Proudly return your sandwich:

  return len;

💻 The Code

// Sandwiched symmetry in Java
public int longestPalindrome(String s) {
    int[] freq = new int[128];
    for (char c : s.toCharArray()) freq[c]++;
    int len = 0;
    for (int f : freq) len += (f / 2) * 2;
    if (len < s.length()) len++;
    return len;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Case matters: ‘A’ is not ‘a’. Trying to pair them is like putting ketchup on pancakes.
• All uniques: Only one lonely letter sits in the middle. That’s not a bug, it’s just…sad.
• All the same letter: You win. You get the whole string, no drama.
• Non-ASCII? Use a HashMap instead of int[128]. Or live dangerously.
• Time & Space: O(n) to count, O(1) extra space (if ASCII). No table wrestling, no tears.

🧠 Interviewer Brain-Tattoo

If you’re checking for palindromes here, you’re doing extra credit for another class. Building palindromes? Now you’re thinking like a greedy symmetry chef—go big, go odd, go home.