Problem
You are given a strings. Return the longest palindromic substring in s. A substring consists of consecutive characters from the original string.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
s = "babad"Output
"bab"Solution
This problem can be solved using Dynamic Programming with Memoization.A substring from index
left to right is a palindrome if its first and last characters are equal and the substring between them is also a palindrome.
The base cases are simple. A single character is always a palindrome, and two characters form a palindrome when both characters are equal.
We recursively check different substrings and store whether each range is a palindrome in a memoization table to avoid recalculating the same range.
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
Boolean[][] memo = new Boolean[n][n];
String result = "";
for (int left = 0; left < n; left++) {
for (int right = left; right < n; right++) {
if (isPalindrome(s, left, right, memo) && right - left + 1 > result.length()) {
result = s.substring(left, right + 1);
}
}
}
return result;
}
private boolean isPalindrome(String s, int left, int right, Boolean[][] memo) {
// A single character or empty range is a palindrome.
if (left >= right) {
return true;
}
// Return the cached result.
if (memo[left][right] != null) {
return memo[left][right];
}
// Check the outer characters and the substring inside them.
return memo[left][right] = s.charAt(left) == s.charAt(right)
&& isPalindrome(s, left + 1, right - 1, memo);
}
}
Complexity
There areO(nĀ²) possible substrings, and each palindrome check is calculated only once.
Therefore, the time complexity is
O(nĀ²), and the memoization table requires O(nĀ²) space.
Tabulation Approach
We can also solve the problem using a bottom-up DP table.Let
dp[i][j] represent whether the substring from index i to j is a palindrome.
A substring is a palindrome when its first and last characters are equal and either the substring contains at most two characters or the inner substring is already known to be a palindrome.
dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1])class Solution {
public String longestPalindrome(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
String result = "";
for (int left = n - 1; left >= 0; left--) {
for (int right = left; right < n; right++) {
if (s.charAt(left) == s.charAt(right)
&& (right - left < 2 || dp[left + 1][right - 1])) {
dp[left][right] = true;
if (right - left + 1 > result.length()) {
result = s.substring(left, right + 1);
}
}
}
}
return result;
}
}
Complexity
The DP table checks every possible substring, resulting inO(nĀ²) time complexity. The DP table requires O(nĀ²) space.
Optimized Approach
A more space-efficient approach is to expand around every possible center.Every palindrome has a center. For an odd-length palindrome, the center is a character. For an even-length palindrome, the center lies between two characters.
For every index, we expand in both directions while the characters are equal and keep track of the longest palindrome found.
class Solution {
public String longestPalindrome(String s) {
int start = 0;
int end = 0;
for (int i = 0; i < s.length(); i++) {
int oddLength = expand(s, i, i);
int evenLength = expand(s, i, i + 1);
int maxLength = Math.max(oddLength, evenLength);
if (maxLength > end - start + 1) {
start = i - (maxLength - 1) / 2;
end = i + maxLength / 2;
}
}
return s.substring(start, end + 1);
}
private int expand(String s, int left, int right) {
while (left >= 0 && right < s.length()
&& s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}
}
Complexity
There are2n - 1 possible centers, and expanding from a center can take up to O(n) time. Therefore, the total time complexity is O(nĀ²).
Only a constant number of variables is used apart from the input string.
