Hash MapsEasyO(n) time · O(1) space

Longest Palindrome

Mahabharata — The Symmetric Formation — Building the Longest Mirror Army

वामभागः दक्षिणभागस्य प्रतिबिम्बम् — पूर्णं पालिन्द्रोमम्। सम-युग्मानि उभयोः — एकं विषमं मध्ये॥

*Left mirrors right — the perfect palindrome. Even pairs on both sides — one odd stands in the center.*

The Story

Given a string with uppercase and lowercase letters, find the length of the longest palindrome that can be built using those characters.

For `s = "abccccdd"`: longest palindrome = `"dccaccd"` or similar, length = 7.

Yudhishthira was arranging warriors in a palindromic formation — identical on both flanks, with at most one warrior in the center.

**Key insight for palindrome construction:** - Characters with EVEN frequency contribute all their occurrences (both sides) - Characters with ODD frequency contribute all but one (floor to even): `count - count%2 = (count/2)*2` - At most ONE character with odd frequency can be the CENTER of the palindrome

```java int[] f = new int[128]; for (char c : s.toCharArray()) f[c]++; int len = 0; boolean hasOdd = false; for (int x : f) { len += (x / 2) * 2; // Use even portion if (x % 2 == 1) hasOdd = true; } return len + (hasOdd ? 1 : 0); // Add center if any odd ```

Trace `"abccccdd"`: Frequencies: a=1, b=1, c=4, d=2 - a=1: contributes 0 (odd, hasOdd=true) - b=1: contributes 0 (odd, hasOdd=true) - c=4: contributes 4 - d=2: contributes 2 len = 6. hasOdd = true. Return 6+1 = 7 ✓

"We use all even characters fully," Yudhishthira noted. "For odd characters, we use all but one (making them effectively even). Then one odd character can stand alone in the center."

The Permutation Checker

Try all permutations of the string. Check if each is a palindrome. Return the length of the longest. Exponential time — infeasible.

java

// Only practical insight: any string formed from these chars is a palindrome
// if at most one char has odd frequency.
// The maximum palindrome length = sum of even portions + 1 (if any odd)
// The 'brute force' IS the observation — no simpler approach exists
public int longestPalindromeBruteForce(String s) {
    Map<Character, Integer> freq = new HashMap<>();
    for (char c : s.toCharArray()) freq.merge(c, 1, Integer::sum);
    int len = 0; boolean hasOdd = false;
    for (int cnt : freq.values()) {
        if (cnt % 2 == 0) len += cnt;
        else { len += cnt-1; hasOdd = true; }
    }
    return len + (hasOdd ? 1 : 0);
}

Yudhishthira's Symmetric Wisdom

Count char frequencies. Sum (count/2)*2 for each char (even portions). If any count was odd, add 1 for the center. O(1) space with int[128] for ASCII characters.

java

public int longestPalindrome(String s) {
    int[] f = new int[128];  // ASCII
    for (char c : s.toCharArray()) f[c]++;
    int len = 0;
    boolean hasOdd = false;
    for (int x : f) {
        len += (x / 2) * 2;  // Use pairs
        if (x % 2 == 1) hasOdd = true;
    }
    return len + (hasOdd ? 1 : 0);
}

Step-by-Step Walkthrough

s="ccc"
f: c=3
len=(3/2)*2=2. hasOdd=true.
Return 2+1=3 ✅ ("ccc" is already a palindrome of length 3)

Deep Insight

**Two formulations for the same result:** 1. `len += (x/2)*2` — uses integer division to get even portion 2. `len += x - (x%2)` — subtracts the odd remainder

Both give the same result.

**Uppercase vs lowercase:** 'A' and 'a' are DIFFERENT characters. Using `int[128]` (ASCII) handles both. They cannot pair with each other.

**Why at most one center character?** A palindrome reads the same forward and backward. The center character (if any) is unique — it's the only position that doesn't need a mirror. So only ONE character can be odd-frequency and placed in the center.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n)	O(1)	Same as optimal — counting IS the solution
Optimal	O(n)	O(1)	int[128] fixed array — O(1) space

Pattern Recognition

✅ Longest palindrome from character set
✅ Sum (count/2)*2 for each character
✅ Add 1 if any character has odd count (center)
✅ O(1) space with fixed ASCII array

**LeetCode Trigger Phrases:**
→ "longest palindrome" from given characters
→ Build palindrome using frequency analysis
→ "at most one odd-frequency character"

Bhagavad Gita 13.27

समं सर्वेषु भूतेषु तिष्ठन्तं परमेश्वरम्। विनश्यत्स्वविनश्यन्तं यः पश्यति स पश्यति॥

One who sees the Supreme Lord equally present in all beings, the imperishable within the perishable — that person truly sees.

Connection: The palindrome is symmetry made manifest — what is on the left mirrors what is on the right, just as the Supreme is equally present on all sides. The frequency analysis sees all characters equally, pairing them in perfect symmetry. The center character, if it exists, is like the indivisible Self at the heart of all symmetry — the one element that needs no mirror because it reflects itself. The longest palindrome maximizes this sacred symmetry.