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.length <= 2000s consists of lowercase and/or uppercase English letters only.Problem Overview: Given a string of uppercase and lowercase letters, determine the length of the longest palindrome that can be built using those characters. Characters are case-sensitive, so 'A' and 'a' count as different letters. You can rearrange the characters in any order, but each character can only be used as many times as it appears.
Approach 1: Frequency Counting (O(n) time, O(k) space)
This approach uses a hash table to count how many times each character appears in the string. A palindrome works by pairing identical characters symmetrically around the center. For every character with frequency f, you can use f / 2 pairs, contributing 2 * (f / 2) characters to the palindrome length. If any character has an odd frequency, one leftover character can be placed in the center of the palindrome. Iterate through the frequency map, sum all even contributions, and add one extra character if any odd count exists. This approach is straightforward and works for any character set because the hash map dynamically tracks frequencies.
The key insight is that palindrome construction only cares about pairs of characters. Every pair contributes two characters to the final length. Odd counts are mostly usable except for one leftover character, and only one such leftover can occupy the center. The algorithm scans the string once to build the frequency map and once more to compute the length, giving O(n) time complexity with O(k) space where k is the number of unique characters.
Approach 2: Set Usage for Odd Counting (O(n) time, O(k) space)
This method tracks characters with odd occurrences using a set. Iterate through the string and toggle each character in the set: insert it if it's not present, remove it if it already exists. At the end of the scan, the set contains exactly the characters with odd frequencies. The longest palindrome uses all characters except the extra ones from odd counts. If the set size is odd, then odd - 1 of those characters must lose one occurrence to form pairs. The palindrome length becomes n - max(0, odd - 1).
This solution works because each toggle operation effectively pairs characters as they appear. Characters appearing an even number of times cancel out of the set. Only odd counts remain. The approach uses constant-time set operations and a single pass over the string, making it efficient for problems involving parity tracking. It also demonstrates a clean application of greedy reasoning with character pairing and leverages fast membership checks from a hash table based structure.
Recommended for interviews: The frequency counting approach is the most commonly expected solution. It clearly demonstrates understanding of palindrome structure and character pairing while keeping the logic easy to explain. The set-based approach is equally optimal and sometimes preferred for its elegance, but interviewers usually expect candidates to first reason about frequency counts in a string problem like this.
This approach involves counting the frequency of each character in the string and calculating the length of the longest possible palindrome based on those frequencies. The key insight is that even frequency counts can completely contribute to a palindrome, while only one odd frequency character can be used once in the center of the palindrome.
This C program counts the frequency of each character using an array and then calculates the longest palindrome length by adding pairs of characters. If there's an odd frequency character, it is used as a center of the palindrome once, if needed.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) - where n is the length of the string as we iterate through the string to count character frequencies.
Space Complexity: O(1) - We only use a fixed-size array of 128 elements to store character frequencies.
This approach leverages a set data structure to efficiently keep track of characters with odd frequencies. A character encountered an odd number of times will toggle its presence in the set. The result is derived from the total number of characters and the size of this set.
In this C solution, a boolean array or bitmap is utilized to track odd occurrences via toggling. The construction of the palindrome length relies on the simple set logic transformation.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) - Each character is processed independently.
Space Complexity: O(1) - Fixed memory allocation for set representation.
| Approach | Complexity |
|---|---|
| Approach 1: Frequency Counting | Time Complexity: O(n) - where n is the length of the string as we iterate through the string to count character frequencies. |
| Approach 2: Set Usage for Odd Counting | Time Complexity: O(n) - Each character is processed independently. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Counting (Hash Map) | O(n) | O(k) | General case. Most intuitive approach for explaining palindrome construction in interviews. |
| Set Tracking for Odd Counts | O(n) | O(k) | When you want a concise implementation that tracks odd/even frequency parity in a single pass. |
Longest Palindromic Substring - Python - Leetcode 5 • NeetCode • 629,123 views views
Watch 9 more video solutions →Practice Longest Palindrome with our built-in code editor and test cases.
Practice on FleetCode