Code Interview Prep: Longest Palindrome (Python)

Cover picture by MARIOLA GROBELSKA


In this article, I will present one way to solve the code interview problem "longest palindrome" and its implementation in Python.

Problem statement:

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
Explanation: The longest palindrome that can be built is "a", whose length is 1.

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

source: https://leetcode.com/problems/longest-palindrome/description

What is a palindrome?

A palindrome is a word, number, phrase or sequence of symbols that reads the same from left to right and from right to left. Some examples include kayak, bob, racecar, madam.

Please note that in this exercise, a palindrome consists of letters but does not have to be a word from the dictionary. Sequences such as abccccdd are totally valid as we can see in the examples in the problem statement.

The "pocket mirror strategy"

An helpful way to think about the problem is to visualize it and for that we can build an analogy with a pocket mirror or an A4 paper sheet (yes, that's odd but that's really helful!).

Any of those "objects" is made of 2 symmetrical parts and can be folded in 2. For example, for the word woooow, the two symmetrical parts are woo and oow.

In other words, to be a palindrome, a given character must be present the same amount of time in the first part and in the second part of the word. In our example w appears 1 time in each part (2 times in total) and o appears 2 times in each part (4 times in total).

We can notice that the total number of occurrences for each letter is always an even number. So if we count the maximum even number of occurrences of each character and sum it all, we are already able to find the longest palindrome!

Edge case

A palindrome can have one middle character (such as Y in KAYAK). This is the only character that can appear an odd number of times in the palindrome.

While we are doing the sum of the maximum even number of occurrences of each character in the previous step, we can then check if there is at least one character that appears an odd number of times in the word and if so, add one to the final result.

And that's it! We are done.

Summarizing

Let's summarize the different steps:
1/ Count the maximum even number of occurrences for each character in the word and sum it all. To do that, we first count the total number of occurrences. Then we divide the obtained number by 2 (division with remainder) and multiply the result by 2.
For example, if we have 9 as total number of occurrences, we'll get:
9//2 = 4
4*2 = 8
The maximum even number of occurrences for the char is 8


2/ Check if there is at least one character that appear an odd number of times in the word, if so add 1 to the sum

Implementation in Python

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: int
        """
        # s_dict is a dictionary with characters as key and number of occurrences as value - for example "a": 2
        s_dict = {}
        # length is an int variable that will store the length of the longest palindrome
        length = 0
        has_odd_occurrence = False
        # count occurrences for each char in s
        for s_char in s:
            if s_char in s_dict:
                s_dict[s_char] += 1
            else:
                s_dict[s_char] = 1
        # count the maximum even number of times each char appears and increment length
        for count in s_dict.values():
            length += count // 2 * 2
            # check if there is at least one character that appears an odd number of times
            if count % 2 == 1:
                has_odd_occurrence = True
        # if true add one to final result
        return length +1 if has_odd_occurrence else length

---

Complexity

We iterate once over the string and once over dictionary values (same length as s). The time complexity is then O(2n), which is O(n).

We have a dictionary which size is proportional to the number of unique characters in s although limited since the character set is made of English lower and/or uppercase letters only. The space complexity can be considered O(1) in some cases but is O(n) in the worst case.

---

You reached the end of this article :)
I hope you enjoyed learning about the Longest Palindrome problem. You are welcome to share your thoughts in the comments. You can also learn more about me and/or get in touch in the About me section just below.


About me
I’ve been working in tech for 7 years, and have worn many hats as a startup co-founder, and in roles such as technical marketing and developing partnerships to drive audience and revenue.

I’ve been a freelance software engineer (back-end) and technical writer since 2021, and am active in open-source communities as a mentor and 2023 PyData Impact Scholar.

I’ve created a Python package called natholi (national holidays for 200+ countries in one line of code) and contributed to the open-source Amplify app to enable climate-change action. I am also a LGBT and neurodivergent person 🌈

If you want to chat about tech careers, connect with me on LinkedIn or book a call with me here.