Longest Palindrome

Easy
220.

Longest Palindrome

Longest Palindrome is an easy coding problem on strings, hash table and greedy, asked in Amazon, Google and Bloomberg interviews.

Given a string s of upper and lowercase letters, return the length of the longest palindrome that can be built using those letters, in any order. Case matters: "Aa" is not a pair.

Example 1

Input
s = "abccccdd"
Output
7
Explanation
One longest palindrome is "dccaccd".

Example 2

Input
s = "a"
Output
1

Example 3

Input
s = "bb"
Output
2

Constraints

  • 1 <= s.length <= 40
  • s consists of upper and lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var longestPalindrome = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Longest Palindrome — Solution in Python, Java & C++

Longest Palindrome solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Longest Palindrome is an easy coding problem on strings, hash table and greedy, asked in Amazon, Google and Bloomberg interviews.

Problem statement

Given a string s of upper and lowercase letters, return the length of the longest palindrome that can be built using those letters, in any order. Case matters: "Aa" is not a pair.

Example 1

Input: s = "abccccdd"
Output: 7
Explanation: One longest palindrome is "dccaccd".

Example 2

Input: s = "a"
Output: 1

Example 3

Input: s = "bb"
Output: 2

Constraints

  • 1 <= s.length <= 40
  • s consists of upper and lowercase English letters.

Hints for Longest Palindrome

  1. Hint 1

    A palindrome uses every letter an even number of times, except possibly one letter in the exact middle.

  2. Hint 2

    So take the largest even number below or equal to each letter's count.

  3. Hint 3

    If any letter had an odd count, one leftover can still sit in the centre — add 1.

How to solve Longest Palindrome

Pairs of equal letters can be mirrored around the centre; take the even part of every count, and add one more if any count was odd to occupy the middle.

Approach

  1. Count every character.
  2. Sum count - (count % 2) over all characters.
  3. If any count is odd, add 1.

Why it works

A palindrome uses each letter an even number of times except at most one letter in the exact centre. Taking the largest even number ≤ each count uses the maximum pairs, and a single odd leftover fills the centre.

Complexity

  • Time — O(n)
  • Space — O(1) — 52 possible letters

Pitfalls

  • Case-sensitive: A and a do not pair.
  • Add the centre once, not once per odd count.

Reference solution

Python

def longestPalindrome(s: str) -> int:
    count = {}
    for ch in s:
        count[ch] = count.get(ch, 0) + 1
    total = 0
    has_odd = False
    for c in count.values():
        total += c - (c % 2)
        if c % 2 == 1:
            has_odd = True
    return total + (1 if has_odd else 0)

Java

public static int longestPalindrome(String s) {
    int[] count = new int[128];
    for (int i = 0; i < s.length(); i++) count[s.charAt(i)]++;
    int total = 0;
    boolean hasOdd = false;
    for (int c : count) {
        total += c - (c % 2);
        if (c % 2 == 1) hasOdd = true;
    }
    return total + (hasOdd ? 1 : 0);
}

C++

int longestPalindrome(string s) {
    int count[128] = {0};
    for (char ch : s) count[(int) ch]++;
    int total = 0;
    bool hasOdd = false;
    for (int i = 0; i < 128; i++) {
        total += count[i] - (count[i] % 2);
        if (count[i] % 2 == 1) hasOdd = true;
    }
    return total + (hasOdd ? 1 : 0);
}

JavaScript

var longestPalindrome = function(s) {
    const count = new Map();
    for (let i = 0; i < s.length; i++) {
        count.set(s[i], (count.get(s[i]) || 0) + 1);
    }
    let total = 0, hasOdd = false;
    count.forEach(function(c) {
        total += c - (c % 2);
        if (c % 2 === 1) hasOdd = true;
    });
    return total + (hasOdd ? 1 : 0);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets