What is the Longest Palindromic Substring?

A common coding interview question involves finding the longest palindromic substring within a given string. A palindrome is a sequence that reads the same backward as forward, such as "madam" or "racecar." In this article, we will explore different methods to solve this problem, focusing on the most efficient one.

Brute Force Method

The brute force method involves checking all possible substrings of the given string to identify palindromic substrings, and then determining the longest among them. This approach has a time complexity of O(n^3), where n is the length of the string. Here’s how the basic algorithm works:

Generate all possible substrings of the string.
For each substring, check if it is a palindrome.
Keep track of the longest palindromic substring found.

Here is a simple implementation in Python:

python

1def is_palindrome(s):
2    return s == s[::-1]
3
4def longest_palindromic_substring_brute_force(s):
5    max_length = 0
6    longest_substring = ""
7    
8    for i in range(len(s)):
9        for j in range(i + 1, len(s) + 1):
10            substring = s[i:j]
11            if is_palindrome(substring) and len(substring) > max_length:
12                max_length = len(substring)
13                longest_substring = substring
14                
15    return longest_substring

Expand Around Center Method

A more efficient method to find the longest palindromic substring is the expand around center technique. The idea is to consider every character (or pair of characters) in the string as a potential center of a palindrome, and then expand outwards as long as we keep finding matching characters.

This approach works in O(n^2) time, which is much better than the brute force method. Below is a Python implementation:

python

1def longest_palindromic_substring_expand_center(s):
2    def expand_from_center(left, right):
3        while left >= 0 and right < len(s) and s[left] == s[right]:
4            left -= 1
5            right += 1
6        return s[left + 1:right]  # Return the palindromic substring
7
8    longest_substring = ""
9    
10    for i in range(len(s)):
11        # Odd-length palindromes
12        odd_palindrome = expand_from_center(i, i)
13        if len(odd_palindrome) > len(longest_substring):
14            longest_substring = odd_palindrome
15        
16        # Even-length palindromes
17        even_palindrome = expand_from_center(i, i + 1)
18        if len(even_palindrome) > len(longest_substring):
19            longest_substring = even_palindrome
20            
21    return longest_substring

Dynamic Programming Approach

Another approach to find the longest palindromic substring is to use dynamic programming. This method stores the results of subproblems (i.e., whether a substring is a palindrome) in a table, to avoid redundant calculations.

The time complexity here is also O(n^2), but it uses O(n^2) space. Here’s an example of the dynamic programming approach in Python:

python

1def longest_palindromic_substring_dp(s):
2    n = len(s)
3    if n == 0:
4        return ""
5    
6    dp = [[False] * n for _ in range(n)]
7    start = 0
8    max_length = 1
9    
10    for i in range(n):
11        dp[i][i] = True  # Single-character palindromes
12        
13    for i in range(n - 1):
14        if s[i] == s[i + 1]:
15            dp[i][i + 1] = True
16            start = i
17            max_length = 2
18            
19    for length in range(3, n + 1):  # length of the substring
20        for i in range(n - length + 1):
21            j = i + length - 1
22            if s[i] == s[j] and dp[i + 1][j - 1]:
23                dp[i][j] = True
24                start = i
25                max_length = length
26                
27    return s[start:start + max_length]

These methods showcase different approaches to solving the longest palindromic substring problem. Each method has its pros and cons, and understanding them will enhance problem-solving skills in coding interviews.