LeetCode — Longest Palindromic Substring
Problem Link: https://leetcode.com/problems/longest-palindromic-substring/
Problem Description: Given a string s, return the longest palindromic substring in s.
Example 1:
Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.Example 2:
Input: s = "cbbd"
Output: "bb"Example 3:
Input: s = "a"
Output: "a"Example 4:
Input: s = "ac"
Output: "a"
Approach Used: Dynamic Programming
Explanation: In this question, we need to a subset of the string which is a palindrome. There can be multiple such subsets, so we need to filter them to the ones which have the maximum length and then send anyone of those. The minimum length of a subset will always be 1 since a single character is always a palindrome and the maximum length can be the length of the string if the whole string is a palindrome.
The brute force way to do is to consider all the substrings possible and for each substring check if it is a palindrome or not. To generate substring of all length and then checking we will need a time complexity of O(N³).
We can reduce this complexity to O(N²) if we think of the approach in a recursive way. To check if a string is a palindrome or not in a recursive way, we can check if the corner characters are same or not and then check that if we remove the corner characters, are the remaining characters palindrome or not. This goes on until we are left with a substring of size 0 or 1. In which case, it will be a palindrome.
To further optimise our recursion, we can save the result of the computation of smaller substrings which will be used for the current substring. This will make our recursive approach into a dynamic programming approach.
Code: (Java)
public String longestPalindromeDp2d(String s) {
boolean[][] lps = new boolean[s.length()][s.length()];
int max_length=Integer.MIN_VALUE;
int ansStart = 0;
int ansEnd=0;for(int curr_length=1; curr_length<=s.length(); curr_length++){
for(int substring_start=0; substring_start<s.length()-curr_length+1; substring_start++){
if(curr_length==1)
lps[substring_start][substring_start]=true;else{
int substring_end = substring_start+curr_length-1;
if(s.charAt(substring_start) == s.charAt(substring_end)){
if(curr_length==2)
lps[substring_start][substring_end] = true;
else
lps[substring_start][substring_end] = lps[substring_start+1][substring_end-1];if(lps[substring_start][substring_end] && max_length<substring_end-substring_start){
max_length = substring_end-substring_start;
ansStart = substring_start;
ansEnd = substring_end;
}
}
else
lps[substring_start][substring_end] = false;
}
}
}return s.substring(ansStart, ansEnd+1);
}
public String longestPalindrome(String s) {
return longestPalindromeDp2d(s);
}
Complexity:
Space Complexity: O(N²). We use a 2-d matrix to store if substrings of different length starting and certain point and ending at a certain point are palindrome or not.
Time Complexity: O(N²). Since we are considering each point as the starting point and all other points(on the right) for each point as the endpoint, we will use two loops and hence more complexity.
The Github link contains code with comments for a better explanation.
Github Link:
https://github.com/siddhaant-jain/LeetCode/blob/master/DailyChallenge/src/CodeFiles/LongestPalindromicSubstring.java
