Longest Palindrome

---

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

---

Constraints:

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

---

Try this Problem on your own or check similar problems:

1. Largest Palindromic Number
2. Longest Palindrome by Concatenating Two Letter Words

Solution:

Java

public int longestPalindrome(String s) {
    if(s.isEmpty()) return 0;

    int[] freqMap = new int[128];
    for(int i = 0; i < s.length(); ++i){
        ++freqMap[s.charAt(i)];
    }

    int totalLength = 0;
    boolean atLeastoneOddPaired = false;
    for(int i = 0; i < freqMap.length; ++i){
        if(freqMap[i] == 0) continue;
        totalLength += freqMap[i] % 2 != 0 ? freqMap[i] - 1 : freqMap[i];
        if(freqMap[i] % 2 != 0) atLeastoneOddPaired = true;
    }

    return totalLength + (atLeastoneOddPaired ? 1 : 0);
}

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
var longestPalindrome = function (s) {
  if (s.length === 0) return 0;

  let freqMap = Array(128).fill(0);
  for (let i = 0; i < s.length; ++i) {
    ++freqMap[s.charCodeAt(i)];
  }

  let totalLength = 0;
  let atLeastOneOddPaired = false;
  for (let i = 0; i < freqMap.length; ++i) {
    if (freqMap[i] === 0) continue;
    totalLength += freqMap[i] % 2 !== 0 ? freqMap[i] - 1 : freqMap[i];
    if (freqMap[i] % 2 !== 0) atLeastOneOddPaired = true;
  }

  return totalLength + (atLeastOneOddPaired ? 1 : 0);
};

Python

class Solution:
    def longestPalindrome(self, s: str) -> int:
        if len(s) == 0:
            return 0

        freqMap = [0] * 128
        for i in range(len(s)):
            freqMap[ord(s[i])] += 1

        totalLength = 0
        atLeastOneOddPaired = False
        for i in range(len(freqMap)):
            if freqMap[i] == 0:
                continue
            totalLength += freqMap[i] - 1 if freqMap[i] % 2 != 0 else freqMap[i]
            if freqMap[i] % 2 != 0:
                atLeastOneOddPaired = True

        return totalLength + (1 if atLeastOneOddPaired else 0)

C++

class Solution {
public:
    int longestPalindrome(string s) {
        if (s.empty()) return 0;

        std::vector<int> freqMap(128, 0);
        for (int i = 0; i < s.length(); ++i) {
            ++freqMap[s[i]];
        }

        int totalLength = 0;
        bool atLeastOneOddPaired = false;
        for (int i = 0; i < freqMap.size(); ++i) {
            if (freqMap[i] == 0) continue;
            totalLength += freqMap[i] % 2 != 0 ? freqMap[i] - 1 : freqMap[i];
            if (freqMap[i] % 2 != 0) atLeastOneOddPaired = true;
        }

        return totalLength + (atLeastOneOddPaired ? 1 : 0);
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

---

Explanation:

First of all palindrome is a string that reads the same both ways (left to right and right to left) for example "kayak". We traverse the whole string input leading to linear time complexity while we also keep a limited size freqMap array which holds counts for all lowercase and uppercase letters where letter mapping to array index is implicitly done in ++freqMap[s.charAt(i)]; leading to constant space complexity. If we have a even number of counts for a letter we can use all of those since they can be paired in palindrome by putting them on each side of the resulting string. If there is odd count for a letter we can use freqMap[i] - 1 (since that will turn it to even count that can distributed on both side of the palindrome we're creating). We also have to remember that we can place one additional character in the middle, for example if we have 4 b's and 1 a, we can make a palindrome "bbabb". We use all letters that have even count, so to put a letter in the middle we have to have at least one letter with odd count.