Leetcode – Longest Palindrome Solution in Python

Spread the love

Introduction

In this in-depth article, we will explore the ‘Longest Palindrome’ problem on Leetcode, examine different approaches to solve it in Python, analyze the time complexity, and understand the underlying concepts involved.

Problem Statement

The ‘Longest Palindrome’ problem is listed as problem number 409 on Leetcode. The problem statement is as follows:

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:

Input: s = "abccccdd"
Output: 7
Explanation: One of the longest palindromes that can be built is "dccaccd", whose length is 7.

Approach 1: Using a Hash Set

  1. Create an empty hash set to keep track of characters.
  2. Initialize a variable count to 0 to store the length of the longest palindrome that can be built.
  3. Iterate through each character in the string s.
  4. For each character, if it is in the hash set, remove it from the set and increment count by 2 (a pair is found which can be part of the palindrome).
  5. Otherwise, add the character to the set.
  6. After the loop ends, if the set is not empty, it means we can add one character in the middle of the palindrome. Increment count by 1 in this case.
  7. Return count.
def longestPalindrome(s):
    char_set = set()
    count = 0

    for char in s:
        if char in char_set:
            char_set.remove(char)
            count += 2
        else:
            char_set.add(char)

    if char_set:
        count += 1

    return count

Time Complexity

The time complexity of this approach is O(n), where n is the length of the string s, as it requires a single pass through the string.

Approach 2: Using a Dictionary (HashMap)

  1. Create an empty dictionary to keep track of the frequency of each character.
  2. Iterate through each character in the string s, and update the frequency in the dictionary.
  3. Initialize a variable count to 0 to store the length of the longest palindrome that can be built.
  4. Iterate through the values in the dictionary, for each value v, add v // 2 * 2 to count.
  5. If count is less than the length of s, it means we can add one character in the middle of the palindrome. Increment count by 1 in this case.
  6. Return count.
def longestPalindrome(s):
    freq_map = {}

    for char in s:
        freq_map[char] = freq_map.get(char, 0) + 1

    count = 0

    for freq in freq_map.values():
        count += freq // 2 * 2

    if count < len(s):
        count += 1

    return count

Time Complexity

The time complexity of this approach is also O(n), where n is the length of the string s.

Conclusion

The ‘Longest Palindrome’ problem on Leetcode is an intriguing problem that involves understanding the properties of palindromes and efficiently keeping track of characters using data structures such as hash sets or dictionaries. The goal is to maximize the number of pairs of characters and, if possible, add an unpaired character in the middle. Both of the approaches discussed have a linear time complexity and provide an efficient solution to the problem.

Leave a Reply