Solution: Longest Palindromic Substring

A naive approach to this problem is to find all possible substrings and select one longest palindromic substring. For example, consider the string “deed”, which contains 10 substrings: “d”, “e”, “e”, “d”, “de”, “ee”, “ed”, “dee”, “eed”, and “deed”. Out of these 10 substrings, six are palindromes: “d”, “e”, “e”, “d”, “ee”, and “deed”. Among these palindromes, the longest palindromic substring is “deed”.

We get the required result, but at what cost? Since we’re checking every possible substring, the total number of substrings in a string of length $n$ is $O(n^2)$. The time required to check whether a string is a palindrome is $O(n)$. Therefore, the time complexity of this algorithm is $O(n^3)$. Since we’re not using any extra space, the space complexity of this algorithm is $O(1)$.

Optimized approach using dynamic programming#

If we look at the example above, we notice that any substring of length $3$ contains a substring of length $1$ at the center. Although we had already checked all substrings of length $1$, our algorithm rechecked them for substrings of longer lengths. This rechecking consumes a lot of time, which can be avoided by storing and reusing the results of the earlier computations. To do this, we can create a lookup table, dp, of size $n \times n$, where $n$ is the length of the input string. Each cell dp[i][j] will store whether the string s[i..j] is a palindromic substring. If the cell dp[i][j] holds the result of the earlier computation, we will utilize it in the $O(1)$ lookup time instead of making a recursive call again.

1. Create a resultant array, res, to store the starting and ending indexes of the longest palindromic substring. Initialize it with$[0, 0]$ depicting that the longest palindromic substring seen so far is the first character of the input string. By definition, any string of length $1$ is always a palindrome.

2. Initialize a lookup table, dp, with FALSE.

3. Base case 1: The diagonal in the lookup table is populated with TRUE, because any cell in the diagonal corresponds to a substring of length $1$, and any string of length $1$ is always a palindrome.

4. Base case 2: We check whether all two-letter substrings are palindromes and update the res and dp accordingly. We do this by iterating over the string, comparing s[i] and s[i+1], and storing the result at dp[i][i+1]. After that, we also update res if the value of dp[i][i+1] is TRUE, which tells us that the two-letter substring was a palindrome.

5. After these base cases, we check all substrings of lengths greater than $2$. However, we only compare the first and the last characters. The rest of the string is checked using the lookup table. For example, for a given string “zing”, we want to check whether “zin” is a palindrome. We’ll only compare ‘z’ and ‘n’ and check the value of dp[1][1], which will tell whether the remaining string “i”, represented by s[1..1], is a palindrome. We’ll take the logical AND of these two results and store it at dp[0][2] because “zin” is represented by the substring s[0..2]. This way, we’ll avoid redundant computations and check all possible substrings using the lookup table.

Let’s look at the following illustration to get a better understanding of the solution:

Let's implement the algorithm as discussed above:

Solution summary#

To recap, the solution to this problem can be summarized as follows:

1. Initialize a resultant array with$[0, 0]$ to store the starting and ending indexes of the longest palindromic substring.

2. Initialize a lookup table with FASLE except for the diagonal, which is initialized with TRUE because any one-letter string is always a palindrome.

3. Check all two-letter substrings and update the resultant array and the lookup table accordingly.

4. After these base cases, we check all possible substrings of lengths greater than $2$. However, it only compares the first and last characters, and the rest of the substring is checked using the lookup table.

   1. Whenever a palindromic substring is found, the resultant array and the lookup table are updated accordingly.

5. After checking all possible substrings, the algorithm terminates and returns the longest palindromic substrings based on the indexes in the resultant array.

Time complexity#

The time complexity of this algorithm is $O(n^2)$, where $n$ is the length of the input string.

Space complexity#

The space complexity of this algorithm is $O(n^2)$.