Longest Palindrome

Data Structures and Algorithms

Statement

Given a string s that contains English alphabet characters, return the length of the longest palindrome that may be composed using those characters. Characters are case-sensitive, so “Aa” isn’t a palindrome.

Constraints

• 1 ≤ s.length() ≤ 10³
• s consists of lowercase and/or uppercase English characters

Solution

"""
production algorithm
"""

from collections import Counter


class Solution:
    def longest_palindrome(self, s):
        """
        time complexity O(n)
        space complexity O(1)
        """
        counter = Counter(s)
        odds, evens = 0, 0

        for character in counter:
            if counter[character] % 2 == 0:
                evens += counter[character]
            else:
                odds += 1
                evens += counter[character] - 1

        if 0 < odds:
            return evens + 1
        return evens

"""
unit tests
"""

from unittest import TestCase
from algorithms.hashmaps.longest_palindrome.solution import Solution


class SolutionTestCase(TestCase):
    def test_zero_odd_number_of_character_occurrences(self):
        # Given
        s = "wwxxxxyyyyyyzzzzzzzz"
        solution = Solution()

        # When
        actual = solution.longest_palindrome(s)

        # Then
        expected = 20
        self.assertEqual(actual, expected)

    def test_some_odd_number_of_character_occurrences(self):
        # Given
        s = "uvvwwwxxxxyyyyyzzzzzz"
        solution = Solution()

        # When
        actual = solution.longest_palindrome(s)

        # Then
        expected = 19
        self.assertEqual(actual, expected)

Strategy

Hash Maps.

Explanation

First, the algorithm counts the characters of the string. It also initializes the counters odds and evens. Both counters will be used to count the number of characters with an odd or even number of occurrences in the string respectively. Then, the characters of the character counter are iterated.

Notice, the evens count is always incremented. That’s because an even number of characters can always be divided in half, such that together they create a palindrome. However, an odd number of characters can only be divided in half once, such that together they create a palindrome. In other words, an odd number of characters can only be included in a palindrome once, where the middle character of the palindrome is the same character as the characters that have an odd number of occurrences in the palindrome.

After iteration completes, if the odds counter is greater than zero, then there was at least one character that has an odd number of occurrences in the input string. Then, return the evens counter incremented by one, in order to add back one character that can create an odd number of occurrences of some character in the palindrome. Otherwise, just return the evens counter, since no extra character can be added back.

Time Complexity

The algorithm iterates all characters of the input string in order to create the counter. The algorithm also iterates all unique characters of the character counter. At most, the number of characters is greater than the number of unique characters. Therefore, the time complexity of the algorithm is O(n), where n is the number of characters in the input string.

Also, notice that the number of unique characters is at most 52, since all characters are lowercase and/or uppercase English characters. In other words, there’s a constant number of unique characters. Therefore, the iteration of characters of the character counter takes constant time.

Space Complexity

At most, the size of the unique character counter is 52, since all character are lowercase or uppercase English characters. In other words, the unique character counter takes constant auxiliary space. Therefore, the auxiliary space complexity of the algorithm is O(1).

Links

data_structures_algorithms/algorithms/hashmaps/longest_palindrome at main ·…