5. Longest Palindromic Substring (Medium)
https://leetcode.com/problems/longest-palindromic-substring/
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad" Output: "bab" Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd" Output: "bb"
Solutions
class Solution {
// Initially, set all the single char as palindrome, then extend out to both sides by one slot every lap.
public String longestPalindrome(String s) {
if (s == null || s.length() == 0) {
return "";
}
int len = s.length();
// keep track of the palindromes
boolean[][] isPal = new boolean[len][len];
int ans = 0;
int startIndex = -1;
// operations for range =1, =2 and >2 are different, three situations
// must be dealt with respectively
for (int range = 1; range <= len; range++) {
// when range length is 1
for (int i = 0, j = 0; i < len && range == 1; i++, j++) {
isPal[i][i] = true;
ans = 1;
startIndex = i;
}
// when range length is 2
for (int i = 0, j = i + 1; j < len && range == 2; i++, j++) {
if (s.charAt(i) != s.charAt(j)) {
continue;
}
isPal[i][j] = true;
ans = 2;
startIndex = i;
}
// when range length > 2
for (int i = 0, j = range - 1; j < len && range > 2; i++, j++) {
if (s.charAt(i) != s.charAt(j)) {
continue;
}
// expand the range of the substring to both sides by one step
// if A[i+1][j-1] is palindromic, so is A[i][j], vice versa
isPal[i][j] = isPal[i + 1][j - 1];
// if A[i][j] is palindromic and longer than previous one,
// update the max length with the new value
if (isPal[i][j] && range > ans) {
ans = range;
startIndex = i;
}
}
}
return s.substring(startIndex, startIndex + ans);
}
}