Solution: Palindromic Substrings

Statement

Given a string, s, return the number of palindromic substrings contained in it. A substring is a contiguous sequence of characters in a string. A palindrome is a phrase, word, or sequence that reads the same forward and backward.

Constraints:

• $1 \leq$ s.length $\leq 1000$

• s consists of only lowercase English characters.

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which to follow based on considerations such as time complexity and implementation constraints.

Naive approach

A naive approach to this problem is to find all possible substrings and count the number of palindromic substrings. For example, consider the string “deed”. The number of substrings contained in “deed” is 10: “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”. Therefore, the number of palindromic substrings in “deed” is six.

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 $O(1)$ lookup time instead of making a recursive call again.

1. First, we initialize a count variable with $0$, which will count the number of palindromic substrings in s.

2. A lookup table is initialized 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 one, and any string of length one is always a palindrome. The number of one-letter palindromic strings (i.e., the number of elements in the diagonal) is also added to the count.

4. Base case 2: We check whether all two-letter substrings are palindromes and update the count 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 increment the count 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 two. 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: