Logo

Kode$word

Longest Palindrome – Building the Maximum Length from Given Letters (LeetCode 409)
Longest Palindrome – Building the Maximum Length from Given Letters (LeetCode 409)

Longest Palindrome – Building the Maximum Length from Given Letters (LeetCode 409)

Using Frequency Counting to Construct the Largest Possible Palindrome

15 views
0
0
HashMapStringGreedyFrequency CountLeetCodeEasy
Github icon

🔗 Problem Link

LeetCode 409 – Longest Palindrome

👉 https://leetcode.com/problems/longest-palindrome/

Introduction

This is one of those problems where you don’t actually need to build the palindrome.

You just need to calculate the maximum possible length of a palindrome that can be formed using the given characters.

The key idea here is understanding:

How palindromes are structured.

Once you understand that, the solution becomes straightforward and elegant.

📌 Problem Understanding

You are given a string s containing:

  1. Lowercase letters
  2. Uppercase letters
  3. Case-sensitive (meaning 'A' and 'a' are different)

You must return:

The length of the longest palindrome that can be built using those characters.

You can rearrange characters in any order.

Example 1

Input: s = "abccccdd"
Output: 7

One possible palindrome:

dccaccd

Length = 7

Example 2

Input: s = "a"
Output: 1

🧠 Key Observation About Palindromes

A palindrome:

  1. Reads the same forward and backward.
  2. Has mirror symmetry.

This means:

  1. Characters must appear in pairs.
  2. At most one character can appear an odd number of times (middle character).

🧠 Intuition Behind the Approach

Let’s think step by step:

  1. Count frequency of each character.
  2. For every character:
  3. If frequency is even → use all of them.
  4. If frequency is odd → use (frequency - 1).
  5. If at least one odd frequency exists → we can place one odd character in the center.

That’s it.

This is a greedy approach.

💻 Your Code

class Solution {
public int longestPalindrome(String s) {
if(s.length() == 1) return 1;
HashMap<Character,Integer> mp = new HashMap<>();
for(int i =0; i < s.length();i++){
mp.put(s.charAt(i),mp.getOrDefault(s.charAt(i),0)+1);
}
int len =0;
boolean odd = false;
for(int a : mp.values()){
if(a%2 == 0){
len+=a;
}else{
len+=a-1;
odd= true;
}
}
if(odd){
return len+1;
}
return len;
}
}

🔍 Step-by-Step Explanation

1️⃣ Edge Case

if(s.length() == 1) return 1;

If there is only one character, the answer is 1.

2️⃣ Frequency Counting

HashMap<Character,Integer> mp = new HashMap<>();
for(int i =0; i < s.length();i++){
mp.put(s.charAt(i),mp.getOrDefault(s.charAt(i),0)+1);
}

We count how many times each character appears.

3️⃣ Build the Palindrome Length

int len = 0;
boolean odd = false;
  1. len → stores palindrome length
  2. odd → tracks whether any odd frequency exists

4️⃣ Process Each Frequency

for(int a : mp.values()){
if(a % 2 == 0){
len += a;
}else{
len += a - 1;
odd = true;
}
}

If frequency is even → use all characters.

If odd:

  1. Use a - 1 (which is even)
  2. Keep track that we saw an odd number

5️⃣ Add Middle Character If Needed

if(odd){
return len + 1;
}

If at least one odd frequency exists → we can place one character in the center.

Otherwise → return len.

🎯 Why This Works

In a palindrome:

  1. All characters must appear in pairs (mirrored sides).
  2. Only one character can be unpaired (center).

So we:

  1. Use all even counts.
  2. Use even portion of odd counts.
  3. Add one center character if possible.

⏱ Complexity Analysis

Time Complexity: O(n)

  1. One pass to count frequencies
  2. One pass over map (max 52 characters: A–Z, a–z)

Space Complexity: O(52) ≈ O(1)

At most 52 distinct characters.

🔥 Cleaner Optimization Idea

We don’t even need a boolean variable.

We can simply:

  1. Add a / 2 * 2 for every frequency
  2. If total length < original string length → add 1

Example optimized version:

class Solution {
public int longestPalindrome(String s) {
HashMap<Character,Integer> mp = new HashMap<>();
for(char ch : s.toCharArray()){
mp.put(ch, mp.getOrDefault(ch, 0) + 1);
}

int len = 0;

for(int count : mp.values()){
len += (count / 2) * 2;
}

if(len < s.length()){
len += 1;
}

return len;
}
}

🏁 Final Thoughts

This problem teaches:

  1. Understanding palindrome structure
  2. Frequency counting
  3. Greedy logic
  4. Handling odd and even counts

It’s a simple but powerful pattern question.

If you truly understand this, you can easily solve problems like:

  1. Palindrome Permutation
  2. Longest Palindrome by Concatenating Two Letter Words
  3. Count Palindromic Subsequences


Related Articles

Check if All Characters Have Equal Number of Occurrences – Frequency Map Approach (LeetCode 1941)

Check if All Characters Have Equal Number of Occurrences – Frequency Map Approach (LeetCode 1941)

Simple HashMap Technique to Validate Equal Character Frequencies

Read Article
Ransom Note – Frequency Counting Made Simple (LeetCode 383)

Ransom Note – Frequency Counting Made Simple (LeetCode 383)

Using HashMap to Validate Character Availability Efficiently

Read Article
Valid Anagram – Frequency Counting Pattern Explained (LeetCode 242)

Valid Anagram – Frequency Counting Pattern Explained (LeetCode 242)

Using HashMap and Array Optimization to Detect Anagrams Efficiently

Read Article
LeetCode 290: Word Pattern – Multiple Ways to Verify Bijection Between Pattern Characters and Words

LeetCode 290: Word Pattern – Multiple Ways to Verify Bijection Between Pattern Characters and Words

Learn How to Solve the Word Pattern Problem Using HashMaps, Bidirectional Mapping, and Index Mapping Techniques

Read Article

Ai Assistant Kas