Leetcode 409: Longest Palindrome

Problem 409: Longest Palindrome

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.

This solution iterates through the characters of the input string s, and for each character, checks if it is already in the Set 'set'. If the character is already in the Set, it means that it can be part of a palindrome, so the count is incremented by 2 (because a palindrome has two identical halves). The character is also deleted from the Set, so that it cannot be counted again. If the character is not in the Set, it is added to the Set.

At the end of the loop, if the length of the input string s is equal to the count, it means that all characters can be used to form a palindrome, so the count is returned as is. If the length of s is not equal to the count, it means that there are some characters left in the Set that can be used to form a palindrome with the existing characters, so the count is incremented by 1 and returned.

We begin by initializing 'count' to 0 and 'set' to a new empty Set.

let count = 0
let set = new Set()

Next, we start iterating through a for loop.

for (let char of s) {
  ...
}

Each iteration checks whether each character is already in the set or not.
If the character is NOT in the set we add it to the set.

for (let char of s) {
  if {
    ...
  } else 
    set.add(char)
}

If the character IS in the set, the count is incremented by 2 and deleted from the set.

for (let char of s) {
  if (set.has(char) {
    count += 2
    set.delete(char)
  } else 
    ...
}

At the end of the loop we need to return the correct count, indicating the longest possible palindrome. Knowing that a palindrome can contain at most 1 single character, we can use a ternary operator to account for this.

return count < s.length ? count + 1 : count

If the count is less than s.length we know there's at least one single character. In our case, count = 6 and s.length = 8. The longest possible palindrome we could return would be a combination of (dcc[x]ccd), where [x] represents a single character from our set. It doesn't matter if it were (dccaccd) or (dccbccd) since the count would still be equal to 7. The [x] represents the '+ 1' in our ternary 'count + 1'.

If the count is NOT less than s.length that means our string has an even count and every character has a matching character creating a complete palindrome. Since it's impossible for the count to be greater than s.length, when the count is not less than s.length it can only mean that count = s.length. Our ternary could be written as either:

return count < s.length ? count + 1: count

or

return count < s.length ? count + 1: s.length

Our final code looks like this:

var longestPalindrome = function(s) {
    let count = 0
    let set = new Set()

    for (let char of s) {
        if (set.has(char)) {
            count+=2
            set.delete(char)
        } else {
            set.add(char)
        }
    }
return count !== s.length ? count + 1 : count
}

The time complexity of this code is O(n), where n is the length of the input string s. This is because the code iterates through each character in the string only once and performs constant time operations on each character.

The space complexity of this code is also O(n), where n is the length of the input string s. This is because the code creates a set to store characters that appear an odd number of times in the string, and the size of the set can be at most half the length of the input string (in the case where all characters in the string appear exactly twice). Therefore, the space required to store the set is proportional to the length of the input string. Additionally, the code uses a constant amount of additional space to store the count variable.

Hope this was helpful. Please leave a comment if anything looks incorrect or if you have any questions.

Happy coding!