Leetcode Daily - August 14, 2020

Longest Palindrome

Link to Leetcode Question

Lately I've been grinding Leetcode and decided to record some of my thoughts on this blog. This is both to help me look back on what I've worked on as well as help others see how one might think about the problems.

However, since many people post their own solutions in the discussions section of Leetcode, I won't necessarily be posting the optimal solution.

Question

(Copy Pasted From Leetcode)

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example "Aa" is not considered a palindrome here.

Note:
Assume the length of given string will not exceed 1,010.

Example:

Input:
"abccccdd"

Output:
7

Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.

My Approach(es)

I won't go over all the code for all attempts but I will explain my approach(es) qualitatively.

Attempt 1 - Determine Logical Conditions For Longest Palindrome Length

(Submission - Accepted)

I ended up approaching this as a logic problem instead of as a computer science problem. The first thing I noticed is that, except for a middle character, palindromes have matching pairs of the same character symmetric with the middle. So if we were to count how many of each unique character we have, all even sets would be able to go on a palindrome, but there is only space for only one odd "spare" letter.

I decided to pseudocode first and then write my code following this blueprint:

• Count each of the letters and store the counts

• Go through each of the counts and start adding them to a sum

  • The sum is the length of the longest palindrome length
  • If a count is even, we add it
  • If the count is odd, and we haven't seen an odd, we add it
  • If the count is odd, and we already added an odd, we add that count minus one (the largest even value we can add)

Submitted Code (Javascript):

var longestPalindrome = function(s) {
    // palindrome can only contain up to one odd set of letters 
    // all even sets of letters work 
    // go through the string and store all the unique letter counts 
    const dict = {}

    for (let i = 0; i < s.length; i++) {
        if (dict[s[i]]) {
            dict[s[i]] += 1
        } else {
            dict[s[i]] = 1
        }
    }

    // make an array of our letter counts to iterate on 
    let letterCount = [] 
    Object.keys(dict).forEach(key => {
        letterCount.push(dict[key])
    })

    // create variables to remember how long our longest palindrome is 
    // as well as whether we have our one odd letter set 
    let sum = 0
    let seenEven = false 
    // start adding up letter sets

    for (let count of letterCount) {
        if (count % 2 === 0) {
            sum += count 
        } else {
            if (!seenEven) {
                // add odd set if haven't seen one yet
                sum += count 
                seenEven = true 
            } else {
                // turn into even set and add 
                sum += count - 1
            }
        }
    }
    return sum
};

Discussion and Conclusions

I think the solution based on logic is very straightforward, and has time and space complexity of O(n) where n is the length of s. There are probably programming and computer science tricks that can optimize this code even further.

For example, I thought about it afterwards and instead of storing whether we have seen an odd or not, we could always add the "evenized" value, for example count - (count%2). Then add the end, if the longest palindrome length sum were less than s.length, we could simply add 1 (there are spare letters left).

Resubmitted Code:

var longestPalindrome = function(s) {
    // palindrome can only contain up to one odd set of letters 
    // all even sets of letters work 
    // go through the string and store all the unique letter counts 
    const dict = {}

    for (let i = 0; i < s.length; i++) {
        if (dict[s[i]]) {
            dict[s[i]] += 1
        } else {
            dict[s[i]] = 1
        }
    }

    // make an array of our letter counts to iterate on 
    let letterCount = [] 
    Object.keys(dict).forEach(key => {
        letterCount.push(dict[key])
    })

    // create variables to remember how long our longest palindrome is 
    // as well as whether we have our one odd letter set 
    let sum = 0

    // start adding up letter sets    
    for (let count of letterCount) {
        sum += count - (count%2)
    }
    if (sum < s.length) sum ++
    return sum
};