Published: Nov 3, 2022
This type of palindrome problems are there. Like Longest Palindrome by Concatenating Two Letter Words, not always, the palindrome string can be created. Often, multiple palindromes can be created. Start from counting the characters or words. Then, check each character whether the count is even or odd. Count those to meet with the requirements, then we can get the answer.
Given a string
swhich 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 here.
1 <= s.length <= 2000
sconsists of lowercase and/or uppercase English letters only.
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.
In this case, the characters are given. Start from counting each character. Then, go over the count table. If the character’s count is even, add the count to the result. If the character’s count is odd, one forms a center element. Add count - 1 to the result. In the end, if the center element is found, add 1. This way, we can find the answer.
class LongestPalindrome: def longestPalindrome(self, s: str) -> int: counts = collections.Counter(s) result = 0 center = False for _, cnt in counts.items(): if cnt % 2 == 0: result += cnt else: result += cnt - 1 center = True if center: result += 1 return result
O(1)– characters are only lower and/or upper case english letters, 52 at most which is constant