Longest Palindrome

The problem description can be found in LeetCode.

Approach

The problem looks confusing at first, but it is actually very straight-forward.

Let's look at some examples in terms of input and output:

"aabb"      -> 4
"aabbcc"    -> 6
"abc"       -> 1
"aabbc"     -> 5
"aaabbbccc" -> 7

One thing we can notice here is that if a character has an even number of occurrences, we can simply consider all of them in our solution.

However, if we have an odd number of occurrences we need to be careful about what we have to take for our solution. Let's take aaabbbccc as an example. A possible solution could be aabbcc., where . can be any character from {a, b, c}. This suggests that we can take |odd occurrences for a certain char| - 1 for our solution, since it gives us as an even number. Moreover, we have to take into account that we can have an extra character coming from such odd number of occurrences (as this example).

Solution

from typing import List


class Solution:
    def longestPalindrome(self, s: str) -> int:
        counter = self.get_chars_counter(s)

        ans = 0
        for i, rep in enumerate(counter):
            if rep % 2 == 0:
                ans += rep
                counter[i] = 0
            else:
                ans += rep - 1
                counter[i] = 1

        if any(counter) == 1:
            ans += 1

        return ans

    def get_chars_counter(self, s: str) -> List[int]:
        # a  b  ...  z  A  B  ...  Z
        # 0  1      25 26 27      51
        m = [0] * 52

        for char in s:
            if char.islower():
                idx = ord(char) - ord("a")
            elif char.isupper():
                idx = ord(char) - ord("A") + 26
            else:
                raise Exception(
                    "expected either lower-case or upper-case character, "
                    f"but got `{char}`"
                )

            m[idx] += 1

        return m

Complexity

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

Where $n$ is the size of the s string.