“This is the sixth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”
Longest palindrome string
Power button link
Given a string containing both uppercase and lowercase letters, find the longest palindrome string constructed from these letters.
Pay attention to case sensitivity during construction. For example, “Aa” cannot be treated as a palindrome string.
Note: The string is assumed to be no longer than 1010.
Example 1:
Input: "abccCCdd" Output: 7 Explanation: The longest palindrome string we can construct is "dCCaccd ", which is 7 in length.Copy the code
Hash table
Train of thought
What is the meaning of the passage?
- Even. A palindrome string is symmetric. If both sides are symmetric except for the same string in the middle, then the number must be even, so all the even numbers must be counted
- An odd number. The middle number can be one (‘s’) or more (‘ SSS ‘). The important thing to note here is that ‘aaaaa’ and ‘BBB’ and ‘CCCCC’ can be counted. For example, ‘bCCAAAAACCb’ can be intercepted as long as the string is greater than 2
- If it’s an even number, you can have an arbitrary 1 in the middle
Clear your head so you can move on
- Count statistics. Declare a map table and start iterating over strings and counting all the different strings in the map table
- The map table of statistical results is traversed, and all the numbers with even numbers are directly counted into the final result res. For an odd number of letters, we need to see if it has 1 digit, and if it has 1 digit, we use odd to record 1; Map [key] -1, odd=1, used in the middle of the palindrome string
- Return final result res (all even numbers) +odd(any letter)
var longestPalindrome = function (s) {
var map = {}
for (var i = 0; i < s.length; i++) {
map[s[i]] ? map[s[i]]++ : (map[s[i]] = 1)}var odd = 0;
var res = 0
for (var key in map) {
if (map[key] % 2= = =0) {
res += map[key]
}
if (map[key] % 2= = =1 && map[key] > 1) {
res += map[key] - 1
odd = 1
}
if (map[key] === 1) {
odd = 1}}return res + odd
};
Copy the code