Teaching Kids Programming – Longest Palindrome String From Set of Characters

Teaching Kids Programming: Videos on Data Structures and Algorithms

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

Example 3:
Input: s = “bb”
Output: 2

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

Longest Palindrome String From Set of Characters

We can use all the characters that appear even number of times e.g. one left, one right always in pairs. We can add one more extra letter in the middle. We can use the Counter in Python to count the number of times that each character appears.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def longestPalindrome(self, s: str) -> int:
        d = collections.Counter(s)
        ans = 0
        odd = 0
        for key in d:
            if d[key] % 2 == 0:
                ans += d[key]
            else:
                ans += d[key] - 1
                odd = 1
        ans += odd
        return ans

class Solution:
    def longestPalindrome(self, s: str) -> int:
        d = collections.Counter(s)
        ans = 0
        odd = 0
        for key in d:
            if d[key] % 2 == 0:
                ans += d[key]
            else:
                ans += d[key] - 1
                odd = 1
        ans += odd
        return ans

The time complexity is O(N) where N is the number of characters in the given string and the space complexity is also O(N) because of the Counter/Dictionary object.

See also: Algorithm to Compute the Length of the Longest Palindrome String

–EOF (The Ultimate Computing & Technology Blog) —