Longest Palindromic Substring - LeetCode

Problem

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.


public class Solution {
    public String longestPalindrome(String s) {
    }
}

public class Solution {

public String longestPalindrome(String s) {

}

Solution

1. Scan the character from left, and make it current position and center. (need consider cases: abcba and abccba)
2. Around the center, move two pointers, one to left, one to right until it is not Palindrome. Get current Palindrome string
3. Compare to the max length Palindrome, and choose a new max length Palindrome.


public class Solution {
    public String longestPalindrome(String s) {
    	if(s == null) return null;
    	if(s.length() == 1) return s;
    	
    	String str = ""; 
    	for(int i = 0; i < s.length(); i++) {
    		final String str1 = getPalindrome(s, i, i);  // in case abcda
    		final String str2 = getPalindrome(s, i, i+1); // in case abccda
    		
    		str = str1.length() > str.length() ? str1 : str;
    		str = str2.length() > str.length() ? str2 : str;
    	}
    	
    	return str;
    }
    
    public static String getPalindrome(String s, int start, int end) {
    	while(start >= 0 && end <= s.length() - 1 && s.charAt(start) == s.charAt(end)) {
    		start--;
    		end++;
    	}
    	return s.substring(start + 1, end);
    }
}