Longest Palindrome

Q: What is the time complexity of Longest Palindrome?

O(n) time with counting: each letter adds 1 to one counter, and adding up the pairs reads 128 counters whatever the length of s . The space is O(1) . Sorting and pairing neighbours costs O(n log n) time and O(n) space.

EasyHashing Greedy

+10

You get a string s of upper and lower case letters. Rearrange its letters to build the longest palindrome you can and return that palindrome's length. You may put the letters in any order and leave some out, but you can use each letter at most as many times as it appears in s.

Upper and lower case are different letters, so Aa is not a palindrome.

Function

longestPalindrome(s: string) → integer

sstring: the letters you may use, upper and lower case
Returnsinteger: the length of the longest palindrome you can build from those letters

Constraints

1 ≤ s.length ≤ 5 × 10⁴
s contains only English letters, a to z and A to Z.
You do not have to use every letter.

Examples

Input: s = "coddyCode"
Output: 5
Explanation: o appears twice and d three times, the rest once. A pair of os, a pair of ds and one leftover letter in the middle give length 5, for example doCod.

Input: s = "Aa"
Output: 1
Explanation: A and a are different letters, so no pair exists. A single letter on its own is a palindrome of length 1.

Input: s = "xxxyyy"
Output: 5
Explanation: Two xs and two ys form pairs, and one leftover letter goes in the middle, as in xyxyx. The last y has no partner and stays out.

Follow-up

Can you return one longest palindrome itself, along with its length, still in O(n) time?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Since you may rearrange, the order of s does not matter, only how many times each letter appears. In a palindrome every letter has a mirror copy on the other side, except at most one letter in the middle. So count the letters, keep every pair, and add one middle letter if any letter is left over.

Sort and pair neighbours

Intuition

Sorting puts equal letters next to each other, so each pair sits side by side. In xxxyyy, the xs at 0 and 1 match: take the pair and move two places. At index 2, x and y differ, so that x stays unpaired and you move one place. The ys at 3 and 4 make a second pair, and the last y is alone. Two pairs give 4, plus one middle letter: 5.

A letter is left over exactly when the pairs used fewer than all n letters, so you need no separate flag. Sorting costs O(n log n) time and the sorted copy takes O(n) space.

Algorithm

Sort the letters of s.
Walk the sorted letters with an index i. If the letters at i and i+1 are equal, add 2 to the length and move two places; otherwise move one place.
If the length is less than the number of letters, add 1 for the middle letter.
Return the length.

def longestPalindrome(s):
    letters = sorted(s)
    n = len(letters)
    length = 0
    i = 0
    while i + 1 < n:
        if letters[i] == letters[i + 1]:
            length += 2  # a pair: one copy on each side of the middle
            i += 2
        else:
            i += 1
    # A letter left without a partner can stand alone in the middle
    if length < n:
        length += 1
    return length

Count each letter

Intuition

Counting gives the same information without sorting. Keep one counter per character code, 128 of them, so A and a land in different counters. A letter that appears c times supplies c rounded down to an even number of letters.

For coddyCode, the pairs of o and d give 4 letters. Five letters are left out, and any one of them can stand in the middle: 5. A second unpaired letter would have no mirror.

One pass over s fills the counters and one pass over the 128 counters adds up the pairs: O(n) time and O(1) extra space (O(n) in R, which first converts s to a vector of codes).

Algorithm

Create 128 counters set to 0, and add 1 to the counter of each letter of s.
For each counter, add the count rounded down to an even number to the length.
If the length is less than the length of s, some count is odd, so add 1 for the middle letter.
Return the length.

def longestPalindrome(s):
    counts = [0] * 128  # one counter per character code, so 'A' and 'a' differ
    for ch in s:
        counts[ord(ch)] += 1
    length = 0
    for count in counts:
        length += count // 2 * 2  # every pair fits, one copy on each side
    # Fewer letters used than s has: some count is odd, so one letter can go in the middle
    if length < len(s):
        length += 1
    return length

Pitfalls and edge cases

Dropping odd counts entirely. A letter that appears 3 times still supplies one pair: xxxyyy gives 5, not 1.
Adding 1 for every odd count. Only one letter fits in the middle, so xxxyyy gives 5, not 6.
Treating A and a as the same letter. Aa has no pair, so the answer is 1, not 2.
Sizing the counters for a to z only. Upper case letters have codes 65 to 90 and fall outside that range; index by the full character code.

Frequently asked questions3

How is Longest Palindrome different from Longest Palindromic Substring?

Here you may rearrange the letters, so only the counts matter and counting solves it in O(n). Longest Palindromic Substring asks for a palindrome that already appears as a block of consecutive letters, and needs another method, such as expanding around each center. For abab this problem answers 4 (abba), the substring version 3 (aba).

What is the time complexity of Longest Palindrome?

O(n) time with counting: each letter adds 1 to one counter, and adding up the pairs reads 128 counters whatever the length of s. The space is O(1). Sorting and pairing neighbours costs O(n log n) time and O(n) space.

Do you have to use every letter of s?

No. Every pair goes in, and at most one unpaired letter goes in the middle. So the answer is the length of s when at most one letter has an odd count, and otherwise the length of s minus the number of letters with an odd count, plus 1.

def longestPalindrome(s):
    # Write code here

Test #1

Test #2

Test #3

Argument

s = "coddyCode"

Expected Output