How do you solve Longest Palindrome on LeetCode?

Longest Palindrome (LeetCode #409) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Character frequencies determine the structure of the longest palindrome.

What is the brute force solution for Longest Palindrome?

The brute force approach for Longest Palindrome is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves generating all possible substrings of the given string and checking if they are palindromes. This method is straightforward but inefficient, as it examines every possible combination. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Longest Palindrome?

Longest Palindrome uses the following concepts: Hash Table, String, Greedy. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Longest Palindrome?

Always consider character frequencies when dealing with string problems. Think about how to optimize your solution from brute force to a more efficient approach. Explain your thought process clearly during the interview; it shows your understanding.

What are common mistakes when solving Longest Palindrome?

Forgetting to check for odd counts when calculating the palindrome length. Not using a HashMap to efficiently count character frequencies.

#409

Longest Palindrome

Easy

Hash TableStringGreedyHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution leverages the frequency of characters in the string. A palindrome can have pairs of characters on both sides, and at most one character can be in the middle. This allows us to efficiently calculate the maximum length without generating substrings.

⚙️

Algorithm

3 steps

1Step 1: Count the frequency of each character in the string using a HashMap.
2Step 2: Initialize a variable to keep track of the length of the palindrome.
3Step 3: For each character count, add the largest even number to the length and check if there's an odd count to potentially add one more character.

solution.py10 lines

1def longestPalindrome(s):
2    from collections import Counter
3    count = Counter(s)
4    length = 0
5    odd_found = False
6    for freq in count.values():
7        length += freq // 2 * 2
8        if freq % 2 == 1:
9            odd_found = True
10    return length + 1 if odd_found else length

ℹ

Complexity note: The time complexity is O(n) because we traverse the string once to count character frequencies. The space complexity is O(n) due to the storage of character counts in a HashMap.

1Character frequencies determine the structure of the longest palindrome.
2Only one character can be in the center of a palindrome if its count is odd.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.