Given a string containing uppercase and lowercase characters, you must determine the length of the longest palindrome that can be formed using the characters in the string.

Examples:

Input: "abccccdd"
Output: 7
Explanation: "dccaccd" or similar

Input: "a"
Output: 1

Input: "Aa"
Output: 1   (case-sensitive, so 'A' ≠ 'a')

---

Problem Understanding

A palindrome reads the same forward and backward.

To build the longest possible palindrome:

• Characters that appear an even number of times can always be fully used.
• Characters that appear an odd number of times can contribute:
  • their largest even portion
  • and possibly one single center character

So the key question becomes:

How many characters can we pair, and can we place one odd character in the middle?

---

Logic Explained in Simple English

Here’s the simplest way to think about it:

1. Count how many times each character appears.
2. For each character:
   • If its count is even → all of it can be used.
   • If its count is odd → use count – 1 (because that is even).
3. After adding all even contributions:
   • If there was at least one odd count, we can add one extra character in the center.

Why this works:

• A palindrome mirrors around the center.
• Pairs are needed on left and right.
• Only one character can sit in the middle without a pair.

So the length equals:

sum of all even counts + largest even parts of odd counts + 1 (if any odd existed)

---

Step-by-Step Approach

1. Create a frequency map for characters.
2. Initialize result length to 0.
3. Loop through each character count:
   • Add (count / 2) * 2 to result.
   • Track whether any count is odd.
4. If any odd count was found, add +1 to result.
5. Return result.

---

Java Implementation

class Solution {
    public int longestPalindrome(String s) {
        int[] freq = new int[128]; // ASCII covers uppercase + lowercase

        for (char c : s.toCharArray()) {
            freq++;
        }

        int length = 0;
        boolean hasOdd = false;

        for (int count : freq) {
            length += (count / 2) * 2;
            if (count % 2 == 1) {
                hasOdd = true;
            }
        }

        if (hasOdd) {
            length += 1;
        }

        return length;
    }
}

---

Dry Run Example

Input:

"abccccdd"

Step 1 — Count characters:

a: 1
b: 1
c: 4
d: 2

Step 2 — Add even contributions:

• c → 4 (even) → add 4 → total = 4
• d → 2 (even) → add 2 → total = 6
• a → 1 (odd) → add 0 → total = 6
• b → 1 (odd) → add 0 → total = 6

Step 3 — Check for odd counts

a and b are odd → so we can add 1 for the center

Final result:

6 + 1 = 7

Output:

7

---

Time and Space Complexity

Time Complexity

O(n)

We scan the string once and process frequency array once.

Space Complexity

O(1)

Fixed-size frequency array (128 or 256), regardless of input length.

---

Common Mistakes and How to Avoid Them

Mistake 1: Treating uppercase and lowercase as the same

In this problem:

'A' and 'a' are different characters

Mistake 2: Forgetting to add central odd character

Only one odd count adds +1.

Mistake 3: Trying to build the actual palindrome

The problem only asks for the length, not the string.

Mistake 4: Assuming half-string length is enough

Pairs must be counted explicitly.

Mistake 5: Using HashMap when ASCII array is simpler

Character range is small.