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.

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.

💪
Level Up Your
Algo Skills

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):

    babad
    10000
    01000
    00100
    00010
    00001
  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:

    babad
    10100
    01010
    00100
    00010
    00001
  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.

Python Solution

1class Solution:
2    def longestPalindrome(self, s: str) -> str:
3        n = len(s)  # Length of the string
4      
5        # Table to store the palindrome status
6        # dp[i][j] will be 'True' if the string from index i to j is a palindrome.
7        dp = [[True] * n for _ in range(n)]
8      
9        start_index = 0  # Start index of the longest palindrome found
10        max_length = 1   # Length of the longest palindrome found, initially 1 character
11      
12        # Bottom-up dynamic programming approach.
13        # Start from the end of the string and move towards the beginning.
14        for i in range(n - 2, -1, -1):  # i is the start index of the substring
15            for j in range(i + 1, n):  # j is the end index of the substring
16                dp[i][j] = False  # Initially set to False
17              
18                # Check if the current substring is a palindrome
19                if s[i] == s[j] and dp[i + 1][j - 1]:
20                    dp[i][j] = True  # Update the palindrome status
21                    # Check if the current palindrome is the longest found so far
22                    if max_length < j - i + 1:
23                        start_index = i
24                        max_length = j - i + 1  # Update max_length
25      
26        # Return the longest palindrome substring
27        return s[start_index : start_index + max_length]
28

Java Solution

1class Solution {
2    public String longestPalindrome(String s) {
3        int n = s.length(); // Get the length of the string.
4        boolean[][] dp = new boolean[n][n]; // Create a dynamic programming (DP) table.
5      
6        // Initialize all substrings of length 1 (single character) as a palindrome.
7        for (boolean[] row : dp) {
8            Arrays.fill(row, true);
9        }
10      
11        int startIdx = 0; // Starting index of the longest palindromic substring found.
12        int maxLength = 1; // Length of the longest palindromic substring found, initialized with length 1.
13      
14        // Build the DP table in a bottom-up manner.
15        for (int i = n - 2; i >= 0; --i) { // Start from the second last character and move backwards.
16            for (int j = i + 1; j < n; ++j) { // Compare it with characters ahead of it.
17                dp[i][j] = false; // Initialize the current substring (i, j) as not palindrome.
18                if (s.charAt(i) == s.charAt(j)) { // If the characters match,
19                    dp[i][j] = dp[i + 1][j - 1]; // Check if removing them gives a palindrome.
20                    // Update the start position and max length if a larger palindrome is found.
21                    if (dp[i][j] && maxLength < j - i + 1) {
22                        maxLength = j - i + 1;
23                        startIdx = i;
24                    }
25                }
26            }
27        }
28      
29        // Extract the longest palindromic substring from the string.
30        return s.substring(startIdx, startIdx + maxLength);
31    }
32}
33

C++ Solution

1#include <vector>
2#include <string>
3
4class Solution {
5public:
6    // Finds the longest palindromic substring in a given string 's'
7    std::string longestPalindrome(std::string s) {
8        int n = s.size(); // Length of the given string
9      
10        // Create a 2D vector 'dp' to store palindrome information.
11        // dp[i][j] will be true if the substring s[i..j] is a palindrome.
12        std::vector<std::vector<bool>> dp(n, std::vector<bool>(n, false));
13
14        int start_index = 0; // Starting index of the longest palindrome found
15        int max_length = 1;  // Length of the longest palindrome found, at least 1 because single characters are palindromes.
16      
17        // Initialize one-character and two-character palindromes
18        for (int i = 0; i < n; ++i) {
19            dp[i][i] = true; // Substrings of length 1 are palindromes.
20            if (i < n - 1 && s[i] == s[i + 1]) {
21                dp[i][i + 1] = true; // Substrings of length 2 are palindromes if both characters are equal.
22                start_index = i; // Update the starting index of the longest palindrome
23                max_length = 2;  // Update the max_length to 2
24            }
25        }
26      
27        // Check for palindromes of length 3 and more
28        for (int len = 3; len <= n; ++len) {
29            for (int i = 0; i < n - len + 1; ++i) {
30                int j = i + len - 1; // Calculate the end index of the current substring
31              
32                // Check if the current substring is a palindrome using previously calculated sub-problems
33                if(s[i] == s[j] && dp[i + 1][j - 1]) {
34                    dp[i][j] = true; // Mark as palindrome
35                 
36                    // Update max_length and start_index if a bigger palindrome is found
37                    if(len > max_length) {
38                        start_index = i;
39                        max_length = len;
40                    }
41                }
42            }
43        }
44      
45        // Extract and return the longest palindrome substring from the original string
46        return s.substr(start_index, max_length);
47    }
48};
49

Typescript Solution

1function longestPalindrome(s: string): string {
2    // Get the length of the string.
3    const length = s.length;
4    // Initialize a 2D array f to track palindromes, initializing all entries to true.
5    const isPalindrome: boolean[][] = Array(length)
6        .fill(0)
7        .map(() => Array(length).fill(true));
8
9    // Initialize a variable to store the starting index of the longest palindrome found.
10    let startIndex = 0;
11    // Initialize a variable to store the length of the longest palindrome found.
12    let maxLength = 1;
13
14    // Loop through the string from end to beginning, adjusting the isPalindrome matrix.
15    for (let i = length - 2; i >= 0; --i) {
16        for (let j = i + 1; j < length; ++j) {
17            // Invalidate the current state since it's not a single character string.
18            isPalindrome[i][j] = false;
19            // If the characters at i and j are the same, check the inner substring.
20            if (s[i] === s[j]) {
21                // Set the state based on the substring inside the current bounds.
22                isPalindrome[i][j] = isPalindrome[i + 1][j - 1];
23                // If the substring is a palindrome and larger than the current maxLength, update maxLength and startIndex.
24                if (isPalindrome[i][j] && maxLength < j - i + 1) {
25                    maxLength = j - i + 1;
26                    startIndex = i;
27                }
28            }
29        }
30    }
31
32    // Get the longest palindrome substring from the given string based on startIndex and maxLength.
33    return s.slice(startIndex, startIndex + maxLength);
34}
35

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.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫