How do you solve Longest Palindromic Substring on LeetCode?

Longest Palindromic Substring (LeetCode #5) can be solved using Brute Force or Optimal Solution (Expand Around Center). The optimal approach is Optimal Solution (Expand Around Center) with O(n²) time complexity and O(1) space complexity. Key insight: Recognizing that palindromes can be expanded around their center helps reduce unnecessary checks.

What is the brute force solution for Longest Palindromic Substring?

The brute force approach for Longest Palindromic Substring is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach checks every possible substring of the input string to see if it is a palindrome. This is straightforward but inefficient because it involves checking many substrings repeatedly. The optimal Optimal Solution (Expand Around Center) approach improves this to O(n²).

What algorithm or data structure is used to solve Longest Palindromic Substring?

Longest Palindromic Substring uses the following concepts: Two Pointers, String, Dynamic Programming. The recommended patterns to study are: Hash Map, Array, Two Pointers.

What are the interview tips for Longest Palindromic Substring?

When you first see this problem, mention that you will explore both brute-force and optimized solutions. Communicate your thought process clearly, especially when transitioning from brute-force to optimal solutions. Mention edge cases like strings with all identical characters or strings with no palindromes longer than one character.

What are common mistakes when solving Longest Palindromic Substring?

Students often forget to check for both odd and even length palindromes, leading to missed cases. Not handling edge cases like single-character strings or empty strings can lead to incorrect results.

Longest Palindromic Substring

Medium

Two PointersStringDynamic ProgrammingHash MapArrayTwo Pointers

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

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

💡

Intuition

Time O(n²)Space O(1)

Instead of checking all substrings, we can take advantage of the properties of palindromes. A palindrome mirrors around its center. Therefore, we can expand around each character (and between characters for even-length palindromes) to find the longest palindrome efficiently.

⚙️

Algorithm

3 steps

1Step 1: Initialize a variable to store the longest palindrome found.
2Step 2: For each character in the string, treat it as the center of a potential palindrome.
3Step 3: Expand outwards while the characters on both sides are equal, updating the longest palindrome when a longer one is found.

solution.py28 lines

1# Full working Python code with comments
2
3def longest_palindrome(s):
4    if len(s) < 1:
5        return ""
6
7    start, end = 0, 0
8
9    for i in range(len(s)):
10        len1 = expand_around_center(s, i, i)  # Odd length
11        len2 = expand_around_center(s, i, i + 1)  # Even length
12        max_len = max(len1, len2)
13
14        if max_len > end - start:
15            start = i - (max_len - 1) // 2
16            end = i + max_len // 2
17
18    return s[start:end + 1]
19
20
21def expand_around_center(s, left, right):
22    while left >= 0 and right < len(s) and s[left] == s[right]:
23        left -= 1
24        right += 1
25    return right - left - 1
26
27# Example usage
28print(longest_palindrome('babad'))  # Output: 'bab' or 'aba'

ℹ

Complexity note: The time complexity is O(n²) because we may expand around each character and in the worst case, we may expand for every character in the string. However, we are not generating substrings explicitly, which saves space.

1Recognizing that palindromes can be expanded around their center helps reduce unnecessary checks.
2Understanding the difference between odd and even length palindromes is crucial for an optimal solution.

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