JavaScript; O(n) time, O(n) space


  • 0
    A

    The crux of this problem is that you are being asked what is the longest palindrome you can create from a given set of characters, not if there is already a palindrome present in the input string. You can think of the characters as building blocks, that you can use in any order, and in any number. That last part is important, because while you can create a palindrome from any even number of characters, it also means that when you get a set of odd characters (potentially many), you need not use all of the odd characters, but only the number of odd characters - 1 (which will give you an even number for any number above 1).

    What the hell does that all mean? Let's do it step-by-step.

    The first thing we want to do is to create a key-value hash of the characters in a string. You can also accomplish the equivalent using some language methods that will give you a ready-made set or hash of the number of times a character occurs in a string - this is assuming we have no such method and must do it manually:

    Note: this is an O(n) time operation, as we must walk through each character in the input string.

    var letters = {}
    var longestPal = 0
    
    for (var i=0;i<s.length;i++) {
            if (letters[s[i]]) {
                letters[s[i]] += 1
            } else {
                letters[s[i]] = 1
            }
        }
    

    So, given a set input, we will produce a hash-map output like so:

    Note: creating this hash-map requires O(n) space, as at worse we could be creating a key:value entry for every letter in a string made up of say, every letter of the alphabet inputted only once.

    inputString = "bbaaaaBBBcdddddd"
    
    letters = {
        "a": 4,
        "b": 2,
        "B": 3,
        "c": 1,
        "d": 6
    }
    

    You can see that "a", "b", and "d" occur an even number of times, while "B" and "c" occur an odd number of times. As a result, you can use all of the "a" (4), "b" (2), and "d" (6) characters, and you can use "B" (3 -1) and "c" (1 - 1), which gives you a total of 14 characters in the longest possible palindrome.

    Note: this is an O(n) time operation, as at worse we could be looping through a set of all the characters in the input string with occurrences === 1

    for (var key in letters) {
            if (letters[key] % 2 === 0) {
                longestPal += letters[key]
            } else {
                longestPal += letters[key]-1
            } 
        }
    

    There is one important caveat here - while you can essentially use almost every character given to you in the input, including all the characters appearing an even number of times, as well as all the characters appearing an odd number of times minus one, a palindrome can accommodate one set of odd characters and still read the same back-to-front.

    Ex: "daaBBBaad"
    

    But further sets of odd characters mess things up:

    "daaBBBZZZaad" - //doesnt work
    "daaBZBZBZaad" - //not quite right
    

    If you want to get really into this, we can go down a proof rabbit hole by stating and finding that a palindrome must read the same at its left-side index as well as its corresponding right-side index (Indexes 0 and string.length-1, 1 and string.length-2, and so on) with only the last odd character in the center allowing us the insert a odd number of the same character ("abcccba"). But I'm not going to worry about that.

    So given we know if there is at least one odd set of characters, we can always get a longer total palindrome by including all the sets of odd characters subtracted by one, with the exception of the longest odd set - we put that entire thing into our palindrome (probably in the center, but there are other ways to make it work). In practice, since you already included the length of the longest odd set - 1, we simply need to track if there is ANY odd set,

    var hasOdd = false
    

    and modify our for-loop condition on hitting an even number:

    for (var key in letters) {
            if (letters[key] % 2 === 0) {
                longestPal += letters[key]
            } else {
                hasOdd = true // <------
                longestPal += letters[key]-1
            } 
        }
    

    And finally, once all is said and done, return the value of longestPal + hasOdd (which in JS will coerce to 1, which is exactly what we want)

    return longestPal + hasOdd;
    

    Our finished code looks like this:

    var longestPalindrome = function(s) {
      
        var letters = {}
        var longestPal = 0
        var hasOdd = false
    
        for (var i=0;i<s.length;i++) {
            if (letters[s[i]]) {
                letters[s[i]] += 1
            } else {
                letters[s[i]] = 1
            }
        }
    
        for (var key in letters) {
            if (letters[key] % 2 === 0) {
                longestPal += letters[key]
            } else {
                hasOdd = true
                longestPal += letters[key]-1
            } 
        }
        // helpers to see whats going on
        console.log(`hasOdd: ${hasOdd}`)
        console.log(`longestPal: ${longestPal}`)
        console.log(letters)
    
        return longestPal + hasOdd;
    };
    

    Hope you found this helpful! Keep on learning!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.