409. Longest Palindrome
Model: qwen2.5-coder:14b
Topics: Hash Table
FAANG asked: 0
Acceptance rate: 52.3%
Problem Breakdown
The problem asks us to find the length of the longest palindrome that can be constructed using the characters from a given string s. The string consists of lowercase and/or uppercase English letters, and the case matters (e.g., “Aa” is not a palindrome).
Inputs:
- A string
scontaining lowercase and/or uppercase English letters.
Outputs:
- An integer representing the length of the longest palindrome that can be built with the characters from
s.
Implicit Constraints or Tricky Edge Cases:
- The string can contain both lowercase and uppercase letters, which are distinct.
- If the string is empty, the longest palindrome would have a length of 0.
- If all characters in the string are unique, the longest palindrome would be of length 1 (using any single character).
- If the string has an even number of each character, the entire string can form a palindrome.
Intuition
A brute-force approach would involve generating all possible substrings and checking if they are palindromes, which is computationally expensive with a time complexity of O(n^3). This is insufficient for large input sizes (up to 2000 characters).
The key insight is that a palindrome can have at most one character with an odd count. All other characters must appear in pairs. Therefore, we can count the occurrences of each character and determine how many pairs we can form. If there’s any character with an odd count, we can place it in the center of the palindrome.
Approach
- Use a hash table (dictionary) to count the occurrences of each character in the string.
- Initialize a variable
lengthto 0 to keep track of the length of the longest palindrome. - Iterate through the counts:
- For each character with an even count, add the entire count to
length. - For each character with an odd count, add the largest even number less than or equal to the count (i.e.,
count - 1) tolength, and mark that we can place one odd character in the center.
- For each character with an even count, add the entire count to
- If at least one character had an odd count, increment
lengthby 1 to account for the central character.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the string. We iterate through the string once to build the hash table and then iterate through the hash table.
- Space Complexity: O(1) or O(k), where k is the number of unique characters in the string (bounded by 52, since there are 26 lowercase and 26 uppercase letters).
Solution
def longestPalindrome(s: str) -> int:
char_count = {}
# Count occurrences of each character
for char in s:
if char in char_count:
char_count[char] += 1
else:
char_count[char] = 1
length = 0
has_odd = False
# Calculate the length of the longest palindrome
for count in char_count.values():
if count % 2 == 0:
length += count
else:
length += count - 1
has_odd = True
# If there's at least one character with an odd count, we can place it in the center
if has_odd:
length += 1
return length
Edge Cases Handled
- Empty String: The function returns 0, as no palindrome can be formed.
- All Unique Characters: The function returns 1, using any single character.
- All Even Character Counts: The function returns the total length of the string.
- Mixed Even and Odd Character Counts: The function correctly forms a palindrome by placing one odd character in the center if possible.