LeetCode Js-409. Longest Palindrome

    LeetCode Js-Hash Table

    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.

    給予一個有大寫或小寫的字串 s,回傳可組成最長的字串。
    (ex.
        左右對稱:noon 
        中心對稱:radar, level)
    

    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
    Explanation: The longest palindrome that can be built is "a", whose length is 1.
    

    Solution:
    1. 設定 hashTable 為 Object literals {}。
    2. 宣告符合字串的長度為 0,條件為 false(如為中心對稱則需 + 1)。
    3. 將 hashTable 中依序放入物件與對應個數。
    4. 將每一個 hashTable 中的字母個數,進行 2 的餘數計算:

    - 剩餘 0: 長度加上此字母的個數
    - 不剩餘 0: 長度加上此字母的個數 - 1 (此數中心點,故須 - 1)
             且符合中心對稱條件。
    

    5. 如果 condition 設定的條件為:

    - condition = true: 長度 + 1
    - condition = false: 長度維持不變
    

    6. 回傳長度。

    Code 1: BigO(n)

    var longestPalindrome = function(s) {
      const hashTable = {}
      let longestLength = 0,
          condition = false
    
      for (let i = 0; i < s.length; i++){
        hashTable[s[i]] = (hashTable[s[i]] || 0) + 1
      }
      for (let value in hashTable) {
        if (hashTable[value] % 2 === 0) {
          longestLength += hashTable[value]
        } else {
          condition = true
          longestLength += hashTable[value] - 1
        }
      }
    
      if (condition) longestLength += 1
      return longestLength;
    };
    

    FlowChart:
    Example 1

    Input: s = "abccccdd"
    longestLength = 0, condition = false
    hashTable = {a: 1}
    hashTable = {a: 1, b: 1}
    hashTable = {a: 1, b: 1, c: 1}
    hashTable = {a: 1, b: 1, c: 2}
    hashTable = {a: 1, b: 1, c: 3}
    hashTable = {a: 1, b: 1, c: 4}
    hashTable = {a: 1, b: 1, c: 2, d: 1}
    hashTable = {a: 1, b: 1, c: 4, d: 2}
    
    step.1
    hashTable[value] % 2 = 1 //{ a: 1}, 1 % 2 = 1
    condition = true
    longestLength += counts[value] - 1 //0 + 1 - 1 = 0
    
    step.2
    counts[value] % 2 = 1 //{ b: 1}, 1 % 2 = 1
    condition = true
    longestLength += hashTable[value] - 1 //0 + 1 - 1 = 0
    
    step.3
    hashTable[value] % 2 = 0 //{ c: 4}, 4 % 2 = 0
    condition = true
    longestLength += hashTable[value] //0 + 4 = 4
    
    step.4
    hashTable[value] % 2 = 0 //{ d: 2}, 2 % 2 = 0
    condition = true
    longestLength += hashTable[value] //4 + 2 = 6
    
    step.5
    condition = true => longestLength += 1 = 6 + 1 = 7 
    (ex.符合中心對稱,故對稱的長度再加上中心點。
    
    return longestLength //7
    

    Example 2

    Input: s = "a"
    longestLength = 0, condition = false
    counts = {a: 1}
    
    step.1
    counts[value] % 2 = 1 //{ a: 1}, 1 % 2 = 1
    condition = true
    longestLength += counts[value] - 1 //0 + 1 - 1 = 0
    
    step.2
    condition = true => longestLength += 1 = 0 + 1 = 1
    
    return longestLength //1
    

    Code 2: BigO(n)

    var longestPalindrome = function(s) {
      const hashTable = new Set()
      let longestLength = 0
    
      for (let key of s) {
        if (hashTable.has(key)) {
          longestLength += 2
          hashTable.delete(key)
        } else {
          hashTable.add(key)
        }
      }
      return longestLength + (hashTable.size > 0 ? 1 : 0);
    };