5 Longest Palindromic Substring g
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.Hint: test wether adding another tail wiil affect cuttent longgest palindromic string to be a palindromic string or not
Solution:
public class Solution {
public String longestPalindrome(String s) {
int currentLength = 0;
String rts = "";
for(int i = 0; i < s.length(); i++){
String cp1, cp2;
//example "xxxxa" current length 3, pointer pointing at "a", two cases:
// 1. adding tail "a" then "xxxa" become p string
// 2. adding tail "a" then "xxxxa" become p string
cp1 = s.substring(Math.max(0,i-currentLength),i+1);
cp2 = s.substring(Math.max(0,i-currentLength-1),i+1);
if(isPalindrome(cp2)&&(i-currentLength-1)>=0) {
currentLength+=2;
rts = cp2;
continue;
}
if(isPalindrome(cp1)&&(i-currentLength)>=0) {
currentLength+=1;
rts = cp1;
continue;
}
}
return rts;
}
private boolean isPalindrome(String s){
for(int i = 0; i < s.length()/2; i++){
if(s.charAt(i)!=s.charAt(s.length()-1-i)) return false;
}
return true;
}
}