The Longest Palindromic Substring is a classic problem of dynamic programming with strings. This question is of a certain type and if you understand it, you can solve many similar problems. In this blog, we will explore different approaches to solving the Longest Palindromic Substring problem, ranging from brute-force methods to more optimized algorithms.
What is Longest Palindromic Substring?
In the Longest Palindromic Substring problem, we have to find the longest contiguous substring within a string that is a palindrome. The substring will be called a palindrome when characters in it read the same forwards and backward.
First, we would be given a string and we have to return the length longest palindromic substring. For example, the substrings of the string "accbc" are: a, ac, acc, accb, accbc, c, cc, ccb, ccbc, c, cb, cbc, b, bc, c. The palindromic substrings are - a, c, cc, cbc, b. The longest palindromic substring is cbc. So, we return 3.
In the realm of computer science, there are multiple approaches to solving this problem. Let's discuss them one by one.
Brute Force Approach
The easiest approach that can we think of would be exploring all the substrings and checking if they are palindromic or not. It is a straightforward but not efficient method for larger strings due to its high time complexity.
Here is the code in Java to implement Brute Force Approach:
For each character at the i-th position, we iterate over i+, i+2---n i.e. length of the substring. For each substring, we check if it is palindromic or not which is done in O(LogN) time. So, the total time complexity comes out to be O(N^2 LogN). As no extra space has been used, the space complexity is O(1).
Optimized Approach using Dynamic Programming
Here are the steps to solving the Longest Palindromic Substring with an Optimized approach:
We create a 2D array of size-string.length() * string.length(). Say, taking the example of string abccbc.
Each of these cells is representing the substring that has been assigned to it that starts from the corresponding row element and ends at the corresponding column element.
So the cell (0,0) says that the substring will start from 'a' and ends at 'a', so we fill the box as a. The cell (0,1) tells that it starts at a and ends at b in the string, so we put "ab" in that cell. Likewise, we fill each cell.
The cells in the lower triangle are not filled as their starting element occurs after the ending element. So a string can't be formed.
Here, from this image, we can notice some important points. The diagonal starting from the cell (0,0) has all the substrings of length 1. The diagonal across the cell (0,1) has all substrings of length 2 and so on.
All the substrings across the 0-th diagonal are palindromic. In 1st diagonal, all the substrings of the same characters are palindromic as they are of size = 2.
In the diagonals 2nd, 3rd, 4th, and 5th we check their extremes and the middle if the characters are the same or not. So we place truly in the cells where we found palindromic substrings.
Now the greatest diagonal having true will be the answer. So we return the answer as diagonal + 1. So here, we have the 3rd diagonal to have the greatest length of the palindromic substring. So we return the answer as diagonal + 1.
The following is the Java Code for the Optimized Approach to solve this problem:
As we traverse over the 2-D array, the time complexity comes out to be O(N^2). And as we take extra space for creating a 2-D dp array, the time complexity comes out to be O(N^2).
Check other Dynamic Programming problems to learn and practice more.
This Longest Palindromic Substring problem is important not only from an interview point of view but also for building concepts. We discussed both the Brute Force approach and the Optimized approach using Dynamic Programming.