Longest Palindromic Substring

Longest Palindromic Substring

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:

Example

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

DP approach

Therefore,

Formula

The base cases are,

DP approach 1

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

Dry Run 1

From the above image, we can see that the palindromic substring found is ‘bbb’ with length 3.

Step 2

Dry Run 2

From the above image, we can see that the palindromic substring found is ‘bbbbb’ with a length of 5

Step-3

Dry Run 3

From the above image, we can see that the palindromic substring found is ‘bbb’ with length 3.

Last Step

Dry Run 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.

Previous Post
Minimum Spanning Tree

Minimum Spanning Tree – Kruskal Algorithm

Next Post
Longest Common Subsequence

Longest Common Subsequence

Total
0
Share