Adobe
Amazon
Apple
Bloomberg
Goldman Sachs
Microsoft
Oracle
Wayfair
Yandex
eBay
tcs
2021-01-24
5. Longest Palindromic Substring
Question:
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"
Constraints:
1 <= s.length <= 1000sconsist of only digits and English letters (lower-case and/or upper-case),
Solution:
dp(i, j) represents whether s(i ... j) can form a palindromic substring, dp(i, j) is true when s(i) equals to s(j) and s(i+1 ... j-1) is a palindromic substring. When we found a palindrome, check if it’s the longest one. Time complexity O(n^2).
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
String res = "";
boolean[][] dp = new boolean[n][n];
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]);
if (dp[i][j] && j - i + 1 > res.length()) {
res = s.substring(i, j + 1);
}
}
}
return res;
}
}
Starting from the first char to check if using the char as its middle point can form a palindorm. Need to consider both odd and even cases.
class Solution {
private int start = 0, len = 0;
public String longestPalindrome(String s) {
if (s == null) {
return "";
}
for (int i = 0; i < s.length(); i++) {
isPalindrome(s, i, i);
isPalindrome(s, i, i + 1);
}
return s.substring(start, start + len);
}
private void isPalindrome(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
if (right - left - 1 > len) {
this.start = left + 1;
this.len = right - left - 1;
}
}
}