grid47 Exploring patterns and algorithms
Sep 27, 2024
5 min read
Solution to LeetCode 409: Longest Palindrome Problem
Given a string consisting of lowercase and/or uppercase English letters, find the length of the longest palindrome that can be constructed from the letters in the string. Letters are case-sensitive.
Problem
Approach
Steps
Complexity
Input: The input is a string s consisting of lowercase and/or uppercase English letters.
Example: For s = 'aabbcc', the longest palindrome is 'abccba', with a length of 6.
Constraints:
• 1 <= s.length <= 2000
• s consists of lowercase and/or uppercase English letters only.
Output: Return the length of the longest palindrome that can be formed with the characters from the string.
Example: For s = 'xyzxy', the longest palindrome is 'xyzxy', with a length of 5.
Constraints:
Goal: To determine the maximum length of the palindrome that can be formed using the characters of the given string.
Steps:
• 1. Count the frequency of each character in the string.
• 2. Add the maximum even occurrences of characters to the result.
• 3. If any character has an odd count, add one extra character to the center of the palindrome.
Goal: The input string will consist of lowercase and/or uppercase English letters, and its length will be between 1 and 2000.
Steps:
• 1 <= s.length <= 2000
• s consists of lowercase and/or uppercase English letters only.
Assumptions:
• The input string contains only valid lowercase and/or uppercase English letters.
• Input: For s = 'aabbcc', the longest palindrome is 'abccba', which has a length of 6.
• Explanation: The palindrome is formed by choosing pairs of characters and placing one in the first half and one in the second half of the palindrome. Since all characters appear an even number of times, all can be used to form a palindrome.
Approach: Count the frequency of each character, then determine the maximum palindrome length that can be formed by using even counts of characters and adding one extra character if any odd counts are present.
Observations:
• A palindrome reads the same forward and backward. To form the longest possible palindrome, we need to use pairs of characters.
• If there are characters with odd occurrences, we can place one of them in the center of the palindrome.
• We need to iterate through the string, count the occurrences of each character, and then determine how many pairs we can form.
Steps:
• 1. Iterate through the string and count the occurrences of each character.
• 2. For each character, add the largest even number of occurrences to the result.
• 3. If any character has an odd count, increment the result by 1 (for the center of the palindrome).
• 4. Return the result as the length of the longest palindrome.
Empty Inputs:
Large Inputs:
• If the string is very large, ensure the solution can handle up to 2000 characters efficiently.
Special Values:
• If the string consists of only one character, the length of the palindrome is 1.
Constraints:
• Handle both uppercase and lowercase letters correctly since they are case-sensitive.
intlongestPalindrome(string s) {
map<char, int> mp;
for(charx: s)
mp[x]++;
bool odd =false;
int res =0;
for(auto [key, val]: mp) {
if(val %2) odd =true;
res += (val/2) *2;
}
return odd? res +1: res;
}
1 : Function Definition
intlongestPalindrome(string s) {
Define the function `longestPalindrome` which takes a string `s` and returns the length of the longest possible palindrome that can be formed using its characters.
2 : Map Initialization
map<char, int> mp;
Initialize a `map` named `mp` that stores the frequency of each character in the string `s`.
3 : Loop Iteration
for(charx: s)
Iterate through each character `x` in the string `s`.
4 : Map Insertion
mp[x]++;
For each character `x`, increment its count in the `map` `mp`.
5 : Boolean Initialization
bool odd =false;
Initialize a boolean variable `odd` to track if there's any character with an odd frequency.
6 : Variable Initialization
int res =0;
Initialize an integer variable `res` to accumulate the total length of the palindrome formed.
7 : Map Iteration
for(auto [key, val]: mp) {
Iterate through each entry in the `map` `mp`, where `key` is the character and `val` is its frequency.
8 : Odd Frequency Check
if(val %2) odd =true;
If the frequency of a character is odd, set the `odd` flag to `true`.
9 : Palindrome Length Calculation
res += (val/2) *2;
For each character, add the largest even number less than or equal to its frequency to `res`. This represents the part of the palindrome that can be used symmetrically on both sides.
10 : Return Statement
return odd? res +1: res;
If there was at least one character with an odd frequency, add 1 to `res` (since we can place exactly one odd character in the middle of the palindrome). Otherwise, return `res` as is.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n), where n is the length of the string, because we only need to iterate through the string once to count the characters and once more to calculate the palindrome length.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) since we only need to store the frequency of characters, which is constant for the 26 lowercase and 26 uppercase English letters.
