5. Longest Palindromic Substring

Problem Description

The goal of this problem is to find the longest palindromic substring within a given string s. A palindromic string is a string that reads the same backward as forward, such as 'radar' or 'level'.

To understand the problem, let's consider what makes up a palindrome:

• A single character is always a palindrome.
• Two characters are a palindrome if they are identical.
• A substring of three or more characters is a palindrome if its first and last characters are the same, and the substring obtained by removing them is also a palindrome.

Given these observations, we need an algorithm that can check for palindromic substrings efficiently and keep track of the longest one found so far.

Intuition

The solution involves Dynamic Programming (DP), an optimization technique that solves complex problems by breaking them into simpler subproblems, storing the solution to each subproblem, and reusing those solutions.

Solution 1: Dynamic Programming The idea is to use a 2D table dp to store whether a substring s[i..j] is a palindrome. We fill this table in a bottom-up manner. For every substring length (from 2 to n), we set dp[i][j] to true if the corresponding substring is a palindrome. Here's the process:

• For substrings of length 1, each is trivially a palindrome.
• For substrings of length 2, they are palindromes if both characters are the same.
• For longer substrings, we check if the first and last characters are the same and if the substring obtained by removing them (dp[i+1][j-1]) is a palindrome.

If dp[i][j] is true, we check if it is the longest palindrome so far. If it is, we update the starting index and maximum length of the palindrome.

Solution 2: Enumerating the Palindrome Center An alternative approach is to consider each possible center of the palindrome (which could be a character or between two characters), and expand outwards from the center to see how far the palindrome can be extended. We keep track of the length and starting point of the longest palindrome found during the process.

Implementing the DP Solution The provided Python code uses the dynamic programming approach. Here's a breakdown of its parts:

• It initializes the dp table (f in the code) to all True for the length 1 substrates, and then iterates backwards over the string.
• For each pair (i, j) it checks if s[i] matches s[j], then it sets f[i][j] to whatever the value at f[i+1][j-1] is, effectively checking if removing the matching characters still leaves a palindrome.
• It keeps track of the start position k and the max length mx of the longest palindrome.

The time complexity of this approach is O(n²) because it examines all possible substrings, making it practical for reasonably short strings.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution to finding the longest palindromic substring employs two main algorithms - Dynamic Programming and Center Expansion. Below is a walkthrough for both.

Dynamic Programming Solution The dynamic programming approach creates a table dp where each entry dp[i][j] records whether the substring s[i..j] is a palindrome.

• Initialize a n by n matrix dp with True values along the diagonal, indicating that all single characters are palindromes.
• Iterate over all possible substring lengths L starting from 2 to the length of the input string n.
• For each length L, iterate over all possible starting indices i from which a substring of length L can be obtained.
• Use the ending index j = i+L-1 to cover the substring of length L starting at index i.
• Set dp[i][j] to True if and only if the end characters match (s[i] == s[j]) and the internal substring s[i+1..j-1] is a palindrome (dp[i+1][j-1] == True).
• Track the starting index and maximum length of the longest palindromic substring found so far.

1dp = [[False] * n for _ in range(n)]
2for i in range(n):
3    dp[i][i] = True  # Base case for one-letter palindrome
4
5mx_len = 1
6start = 0
7
8for L in range(2, n + 1):
9    for i in range(n - L + 1):
10        j = i + L - 1
11        if L == 2:
12            dp[i][j] = (s[i] == s[j])
13        else:
14            dp[i][j] = (s[i] == s[j] and dp[i + 1][j - 1])
15          
16        if dp[i][j] and L > mx_len:
17            mx_len = L
18            start = i

• The time complexity of this approach is O(n^2) as we check all n(n-1)/2 substrings and updating the dp table takes constant time.

In the code, a 2D list f represents the dp table, where we fill the table starting from the second to last row to the first (i = n - 2 to 0) and from left to right (j = i + 1 to n) within each row. This is because dp[i][j] depends on dp[i + 1][j - 1], which is the next diagonal element below it.

1f = [[True] * n for _ in range(n)]
2k, mx = 0, 1
3for i in range(n - 2, -1, -1):
4    for j in range(i + 1, n):
5        if s[i] != s[j]:
6            f[i][j] = False
7        else:
8            if j - i == 1 or f[i + 1][j - 1]:
9                f[i][j] = True
10                if mx < j - i + 1:
11                    k, mx = i, j - i + 1
12        else:
13            f[i][j] = False

Here, the variable k tracks the starting index of the longest palindrome, and mx tracks the length of the longest palindrome.

Center Expansion Solution The center expansion algorithm doesn't require any additional space except for keeping track of the longest palindrome found.

1mx_len = 1
2start = 0
3
4for i in range(n):
5    # Odd Length Palindromes
6    odd_len = expandFromCenter(s, n, i, i)
7    if odd_len > mx_len:
8        mx_len = odd_len
9        start = i - mx_len // 2
10  
11    # Even Length Palindromes
12    even_len = expandFromCenter(s, n, i, i + 1)
13    if even_len > mx_len:
14        mx_len = even_len
15        start = i - (mx_len - 1) // 2
16
17def expandFromCenter(s, n, l, r):
18    while l >= 0 and r < n and s[l] == s[r]:
19        l -= 1
20        r += 1
21    return r - l - 1

Here, the expandFromCenter function checks for the longest palindrome centered at l (for odd lengths) and between l and r (for even lengths), expanding its boundaries outwards as long as the characters match. The lengths of the longest palindromes for both odd and even centers are compared to update the maximum palindrome length mx_len and the starting index start.

The time complexity for this approach is also O(n^2) because each expansion may take O(n) time and there are O(n) potential centers to consider. However, this approach does not use extra space, making it more space-efficient than the dynamic programming approach.

Both approaches are efficient for different scenarios and can be used depending on the space-time trade-off that is more critical for the application at hand.

Example Walkthrough

Let's consider a small example to illustrate the solution approach, specifically the dynamic programming solution.

Suppose the input string is s = "babad". We are interested in finding the longest palindromic substring.

Following the dynamic programming strategy:

1. Initialize the dp table for a string of length 5 (since "babad" is 5 characters long). Each cell dp[i][i] along the diagonal is set to True, representing that every single character is a palindrome by itself. Our dp table initially looks something like this (where 0 indicates False and diagonals are implicitly True):

   b	a	b	a	d
   1	0	0	0	0
   0	1	0	0	0
   0	0	1	0	0
   0	0	0	1	0
   0	0	0	0	1

2. We check two-character substrings (length L = 2) for palindromicity. We notice that "ba" is not a palindrome, "ab" is not a palindrome, "ba" again is not a palindrome, but "ad" is not a palindrome either. So, our dp table does not change.

3. Now we move on to substrings of length 3. We find "bab" is a palindrome and so is "aba". The table updates to:

   b	a	b	a	d
   1	0	1	0	0
   0	1	0	1	0
   0	0	1	0	0
   0	0	0	1	0
   0	0	0	0	1

4. We then proceed to substrings of length 4 and 5 but find no longer palindromes.

5. The dynamic programming algorithm records the longest palindrome we found, which is "bab" starting at index 0 or "aba" starting at index 1, both with a length of 3.

Here is a snippet of Python code that reflects the process for this example:

1s = "babad"
2n = len(s)
3dp = [[False] * n for _ in range(n)]
4for i in range(n):
5    dp[i][i] = True
6mx_len = 1
7start = 0
8
9for L in range(2, n + 1):
10    for i in range(n - L + 1):
11        j = i + L - 1
12        if L == 2:
13            dp[i][j] = (s[i] == s[j])
14        else:
15            dp[i][j] = (s[i] == s[j] and dp[i + 1][j - 1])
16        if dp[i][j] and L > mx_len:
17            mx_len = L
18            start = i
19longest_palindrome = s[start:start+mx_len]
20print(f'The longest palindrome in the string is: "{longest_palindrome}"')

When this code is executed, the longest palindrome "bab" or "aba" (whichever comes first in the updating process) will be printed. The 2D dp matrix serves as a memory that helps avoid recalculating whether a substring is a palindrome, thus saving computational time. Each step relies on the information gathered in the previous steps, making this a bottom-up dynamic programming approach.

Solution Implementation

Time and Space Complexity

The time complexity of the code provided is O(n^2), as it includes two nested loops that both iterate over the string length n. Specifically, the outer loop counts down from n-2 to 0, and the inner loop counts up from i+1 to n, resulting in a quadratic number of steps in terms of the length of the input string s.

The space complexity, however, differs from the reference answer. The code creates a 2D list f sized n by n, which is used to store boolean values representing whether a substring is a palindrome or not. This means the space complexity is not O(1), but in fact O(n^2) as well, because storing these values requires a space proportional to the square of the length of the input string s.

Learn more about how to find time and space complexity quickly using problem constraints.