Solution: Palindromic Substrings
Let's solve the Palindromic Substrings problem using the Dynamic Programming pattern.
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:
s.Length
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
Optimized approach using dynamic programming
If we look at the example above, we notice that any substring of length dp
, of size 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
First, we initialize a
count
variable with, which will count the number of palindromic substrings in s
.A lookup table is initialized with FALSE.
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
.Base case 2: We check whether all two-letter substrings are palindromes and update the
count
anddp
accordingly. We do this by iterating over the string, comparings[i]
ands[i+1]
, and storing the result atdp[i][i+1]
. After that, we also increment thecount
if the value ofdp[i][i+1]
is TRUE, which tells us that the two-letter substring was a palindrome.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 bys[1..1]
, is a palindrome. We’ll take the logical AND of these two results and store it atdp[0][2]
because “zin” is represented by the substrings[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:
Level up your interview prep. Join Educative to access 70+ hands-on prep courses.