Problem Statement
Given a string, we have to find the longest palindromic substring(substring is a sequence of characters that is contiguous within a string. For example, the string “Interviewbit”, “er”, “view”, “bit”,…etc are substrings, but not “tr” as both these characters are not continuous. Whereas palindrome is a word that reads the same backward as forwards. Examples include abba, zzzz, xyyx.
Example:
Input: findnitianhere
Output: indni
Explanation: Substring from index 1 to index 5 is the longest substring.
Input: “acacacb”
Output: 5
Explanation:
Simple Approach
The brute force solution which comes into our mind is to pick all the substrings from a string that is possible and then we will check whether that substring is a palindrome or not.
Hence if we will talk about the implementation part of this approach then we just have to use two loops for finding all the substrings and then one more for checking whether the substance is a palindrome or not. Hence total time complexity of this approach will be N^3.
Implementation of Simple Approach
C/C++ Implementation
Java Implementation
Python Implementation
Time complexity: O(N^3), Where N is the size of the string.
Space complexity: O(1)
Efficient Approach: Dynamic Programming
We can find some patterns in validating palindromes to avoid unnecessary re-computation and improve the brute force approach by memorizing the data.
Consider one example “cbebc”. If we already knew that “beb” is a palindrome, it is obvious that “cbebc” must be a palindrome since the two left and right end letters are the same.
We define P(i,j) as follows
Therefore,
The base cases are,
Implementation of DP Approach
C++ Implementation: Dynamic Programming
Java Implementation: Dynamic Programming
Python Implementation: Dynamic Programming
Time complexity: O(N^2), Where N is the size of the string
Space complexity: O(N^2)
Expand Around Center Approach
In fact, we could solve it in O(n^2) without using any additional array and the time remains the same.
We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only 2n – 1 such center.
Dry Run of Approach
Step 1
From the above image, we can see that the palindromic substring found is ‘bbb’ with length 3.
Step 2
From the above image, we can see that the palindromic substring found is ‘bbbbb’ with a length of 5
Step-3
From the above image, we can see that the palindromic substring found is ‘bbb’ with length 3.
Last Step
From the above image, we can see that the palindromic substring found is ‘bbb’ with length 3.
Implementation Of Above Approach
C++ Implementation of Expand Around Center Approach
Java Implementation of Expand Around Center Approach
Python Implementation of Expand Around Center Approach
Time Complexity: O(N^2)
Space Complexity: O(1)
Practice Questions
Longest Palindromic Substring
Minimum Characters Required To Make String Palindromic
Dynamic Programming
Frequently Asked Questions
What is the longest palindrome sentence?
The largest known palindromic word is saippuakivikauppias (19 letters), which is Finnish for a dealer in lye (caustic soda).
What is the difference between substring and subsequence?
Substring: It is a prefix or suffix of a string.
Subsequence: It is a subset of the string’s character having the same sequential ordering as the original string.
