Longest Palindrome SubString ( LeetCode Question )- All Solutions with Java Code , Brute Force, Dynamic Programming Solution

Problem 

Given a String, Find the Longest Substring which is Palindrome ,

Example  1

Input String : “babadba”, Output is : “aba” since aba is the longest palindrome. Please note – We need to fine the Substring not susequences.

Example 2 

Input String :  “acddca”, Output is :  “acddca” since whole string is palindrome.

 

Approaches 

There are 4 different approaches for solving this problem – Brute Force with O(N^3) , Using Dynamic Programming  O(N^2), Third Choose mid point and Expand in both the sides and last one in O(N) using  Manacher’s Algorithm. Let see all the approaches with code implementation details.

Method 1 – Brute Force 

This is very basic method to solve the problem where we will be generating all the possible SubStrings and then Check whether given string is Palindrome or not. This method takes O(n^3) time complexity. Here is Java Code for its implementation –

Java Code

Time Complexity of above code is – O(N^3), Space Complexity is – O(1)

We can improve the space complexity of above solution using Dynamic Programming which we are going to see below.

Method 2 – Dynamic Programming Approach in O(N^2) Complexity 

Approach 

The Idea here is to avoid checking the palindrome of duplicate substrings i.e. Let say we  have input string -” bacabdbacab”, Now we want to check for palindrome of every Substrinsg individually starting from 0th index

First is – “b”, which is palindrome , Next”ba” which is not palindrome, Next is “bac” which is again not palindrome, Next is “baca” – So now this string can be palindrome if inside string of it “ac” is palindrome i.e. string after first character and string before last character MUST be palindrome then only whole string can be palindrome .

So using DP we can save this repeated duplicate checking and store the results of already traversed strings in a temp table which can be used as follows –

String Starting from ith index and ending at jth index can be Palindrome when – tab[i+1][j-1] is already a palindrome and s[i]==s[j].

This approach will need to populate the starting 2 elements manually, then it can be used for further .

Java Code

Method 3 – Fix Center and Expand Both Sides to Find Longest Palindrome 

Approach 

We have already discussed the method of using Dynamic Programming above, which require extra space of O(N^2) with time complexity of  O(N^2), We can avoid additional space using keeping center index as fixed and checking the palindrome on both the sides till we reaches the extreme boundaries or find the characters are not matching.

This approach will take O(N^2) time complexity.

Java Code

 

%d bloggers like this: