What is the time complexity of Longest Palindrome?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Longest Palindrome?

This problem uses Hash Table, String, Greedy. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Longest Palindrome?

Insight 1: A palindrome can be formed by pairing up characters that appear an even number of times. For example, 'aabbcc' can form 'abccba'. Insight 2: If there's an odd number of occurrences for some characters, we can use all but one of each of these characters to build the palindrome's outer layers.

Which companies ask LeetCode 409. Longest Palindrome in interviews?

This problem is frequently asked at Akamai, HP, Walmart Labs.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Longest Palindrome - LeetCode 409 Solution

Q: How to solve Longest Palindrome?

The solution uses a hash map (or array in the C implementation) to count the frequency of each character in the input string. It then iterates through these frequencies. For each character, if its count is even, we add the entire count to the total length of the palindrome. If the count is odd, we add (count - 1) to the total length, effectively pairing up all possible instances of that character while leaving one instance unused *unless* it can be used as the center character. Finally, if we encountered at least one character with an odd count, we increment the total length by 1 to account for using one of those characters as the palindrome's center.

Longest Palindrome - Complete Solution Guide

Longest Palindrome is LeetCode problem 409, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters. Letters are case sensitive , for example, "Aa" is not considered a palindrome. Example 1: Input: s = "abccccdd" Output: 7 Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7. Example 2: Input: s = "a" Output: 1 Explanation: The longest palindrome that can be built is "a", whose length is 1. Constraints: 1 <= s.lengt

Detailed Explanation

The problem asks us to find the length of the longest palindrome that can be constructed from a given string 's'. The string 's' consists of lowercase or uppercase letters, and case sensitivity matters (e.g., 'A' and 'a' are different). A palindrome is a string that reads the same forwards and backward. The goal is to rearrange the letters in 's' (or use only some of them) to form the longest possible palindrome, and return its length. The input string's length is between 1 and 2000.

Solution Approach

The solution uses a hash map (or array in the C implementation) to count the frequency of each character in the input string. It then iterates through these frequencies. For each character, if its count is even, we add the entire count to the total length of the palindrome. If the count is odd, we add (count - 1) to the total length, effectively pairing up all possible instances of that character while leaving one instance unused *unless* it can be used as the center character. Finally, if we encountered at least one character with an odd count, we increment the total length by 1 to account for using one of those characters as the palindrome's center.

Step-by-Step Algorithm

Step 1: Create a hash map (or array) to store the frequency of each character in the input string 's'.
Step 2: Iterate through the input string 's', and update the frequency count for each character in the hash map (or array).
Step 3: Initialize a variable 'length' to 0. This variable will store the length of the longest palindrome.
Step 4: Initialize a boolean variable 'odd_exists' (or an integer 'oddCount') to false (or 0). This will track if there is an odd number frequency count
Step 5: Iterate through the frequency counts in the hash map (or array).
Step 6: For each frequency count, if it's even, add the count to 'length'.
Step 7: If the frequency count is odd, add (count - 1) to 'length' and set 'odd_exists' to true (or increment 'oddCount' to 1).
Step 8: After iterating through all frequency counts, if 'odd_exists' is true (or 'oddCount' is greater than 0), increment 'length' by 1.
Step 9: Return 'length'.

Key Insights

Insight 1: A palindrome can be formed by pairing up characters that appear an even number of times. For example, 'aabbcc' can form 'abccba'.
Insight 2: If there's an odd number of occurrences for some characters, we can use all but one of each of these characters to build the palindrome's outer layers.
Insight 3: At most one character with an odd count can be placed in the center of the palindrome to maximize the length.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Hash Table, String, Greedy.

Companies

Asked at: Akamai, HP, Walmart Labs.

Longest Palindrome | LeetCode 409

Easy

Hash Table String Greedy

Time: O(n)Space: O(1)

Solution Code

Available in:

class Solution {
    public int longestPalindrome(String s) {
        Map<Character, Integer> charCount = new HashMap<>();
        for (char c : s.toCharArray()) {
            charCount.put(c, charCount.getOrDefault(c, 0) + 1);
        }
        int length = 0;
        int oddCount = 0;
        for (int count : charCount.values()) {
            if (count % 2 == 0) {
                length += count;
            } else {
                length += count - 1;
                oddCount++;
            }
        }
        if (oddCount > 0) {
            length++;
        }
        return length;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 409: Longest Palindrome - Detailed explanation and solution approaches.

Topics

Hash Table String Greedy

Companies

AkamaiHPWalmart Labs

Stats

Difficulty:Easy

Languages:4

Companies:3

Problem #:409

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

9 steps

1
Step 1: Create a hash map (or array) to store the frequency of each character in the input string 's'.
2
Step 2: Iterate through the input string 's', and update the frequency count for each character in the hash map (or array).
3
Step 3: Initialize a variable 'length' to 0. This variable will store the length of the longest palindrome.
4
Step 4: Initialize a boolean variable 'odd_exists' (or an integer 'oddCount') to false (or 0). This will track if there is an odd number frequency count
5
Step 5: Iterate through the frequency counts in the hash map (or array).
6
Step 6: For each frequency count, if it's even, add the count to 'length'.
7
Step 7: If the frequency count is odd, add (count - 1) to 'length' and set 'odd_exists' to true (or increment 'oddCount' to 1).
8
Step 8: After iterating through all frequency counts, if 'odd_exists' is true (or 'oddCount' is greater than 0), increment 'length' by 1.
9
Step 9: Return 'length'.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is O(n) because the dominant operation is iterating through the input string once. The space complexity is O(1) because the hash map (or array) size is constant, independent of the input string's length.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Using a Set

Iterate through the string. If a character is in the set, remove it (meaning we've found a pair). If it's not, add it to the set. At the end, the size of the set represents the number of characters that appeared an odd number of times. Subtract this number from the string length, double it (to account for all the pairs that can form the core palindrome) and add 1 if the set is non-empty.

Time: O(n)Space: O(1)

Trade-offs: This approach can be slightly more readable and intuitive for some. The performance difference should be negligible.

✨

Key Insights

1Insight 1: A palindrome can be formed by pairing up characters that appear an even number of times. For example, 'aabbcc' can form 'abccba'.
2Insight 2: If there's an odd number of occurrences for some characters, we can use all but one of each of these characters to build the palindrome's outer layers.
3Insight 3: At most one character with an odd count can be placed in the center of the palindrome to maximize the length.

📚

Key Terms Explained

For Students

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Greedy Algorithm

Making the best choice at each step without looking ahead.

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: Empty string. Although the problem statement says the string length is between 1 and 2000, if an empty string was passed in (hypothetically), the code would return 0, which is the correct length of the longest palindrome that can be built from an empty string.
Edge case 2: String with a single character (e.g., 'a'). The code correctly returns 1 as the length of the longest palindrome.
Edge case 3: String with all the same characters (e.g., 'aaaa'). The code correctly returns the length of the string.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to add 1 to the length when there is at least one character with an odd count. This misses the possibility of using a single character as the center of the palindrome.

✗Common mistake 2: Incorrectly handling case sensitivity. The problem specifies that uppercase and lowercase letters are distinct, so the solution needs to treat 'A' and 'a' as different characters.

✗Common mistake 3: Confusing palindrome length with the palindrome string itself. The problem only asks for the *length* of the longest palindrome, not the palindrome string itself, which simplifies the problem significantly.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Bioinformatics: Analyzing DNA sequences to identify palindromic sequences, which are often associated with regulatory elements or structural features.

🏦Real-world scenario 2: Data compression: Identifying repeating patterns (which could be palindromic) in data to achieve better compression ratios.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Hash tables trade space for time. Before using one, consider if the problem constraints allow the extra memory. In interviews, always mention this trade-off.

🎯 Interview Tip

Use this problem to demonstrate clean code practices. Variable naming and code organization matter.

⚠️ Watch Out

Don't forget to handle key collisions and null/undefined keys. Consider what happens with duplicate values.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 20, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 13

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 6

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJun 29

❓

Frequently Asked Questions

How do I choose between a hash map and a hash set?

Use a hash set when you only need to track presence/absence of elements (like detecting duplicates). Use a hash map when you need to associate values with keys (like counting frequencies or storing indices). Hash sets use less memory since they only store keys.

What is the sliding window technique for string problems?

Sliding window maintains a "window" of characters with two pointers. Expand the right pointer to include characters, shrink from left when window violates constraints. Useful for substring problems, anagrams, and longest/shortest substring with properties.

What should I learn from easy problems?

Easy problems introduce core patterns that appear in harder problems. Master basic operations (iteration, conditionals, simple data structures), recognize common patterns (counting, searching, basic transformations), and practice explaining your thought process clearly.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Longest Palindrome"?

For this easy-level Hash Table problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether string techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?