LeetCode Notes: Longest Palindrome

#leetcode

Question

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 here.

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

Example 3:

Input: s = "bb"

Output: 2

Constraints:

  • 1 <= s.length <= 2000
  • s consists of lowercase and/or uppercase English letters only.

Solution

Analysis:

  1. First count the number of occurrences of each letter
  2. The even number of letters can be placed directly on both sides of the palindrome string, so you can use it directly. The odd number of letters minus one becomes an even number, which can also be used
  3. In the final special treatment, if there are an odd number of letters, the largest odd number of letters can be placed in the middle position, that is, the final result needs to be +1

Code:

/**
 * @param {string} s
 * @return {number}
 */
var longestPalindrome = function(s) {
    // Used to count the number of times each letter appears
    const count = {}
    for(let i = 0; i <s.length; i++){
        const str = s[i]
        // Repeated letters, number of times +1
        if(str in count){
            count[str] += 1
        }else{// New letters start counting
            count[str] = 1
        }
    }
    let odd = false // Whether to include odd numbers
    let result = 0 // Result statistics
    for(let letter in count){
        const num = count[letter]
        // Letters with an odd number of occurrences, minus one is an even number, and can be placed on both sides of the palindrome
        if(num % 2 === 1){
            result += num-1
            odd = true
        }else if(num % 2 === 0){// Take an even number of letters
            result += num
        }

    }
    // As long as there is an odd number of letters, the largest odd number of letters can be placed in the middle position, so there will be plus one
    return odd ? result + 1: result
};

Reference

Comments