Longest Palindromic Substring

Medium Longest Palindromic Substring

24%

Accepted

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.

Have you met this question in a real interview? 

Yes

Example

Given the string = "abcdzdcab", return "cdzdc".

Challenge

O(n2) time is acceptable. Can you do it in O(n) time.

public class Solution {

    /**

     * @param s input string

     * @return the longest palindromic substring

     */

    public String longestPalindrome(String s) {

        // Write your code here

        if(s == null || s.length() <= 1) return s;

        String maxString = s.substring(0, 1);

        for(int i = 0; i < s.length(); i++){

            String a = getPalindromeLen(i, i, s);

            if(a.length() > maxString.length()){

                maxString = a;

            }

            String b = getPalindromeLen(i, i+1, s);

            

            if(b.length() > maxString.length()){

                maxString = b;

            }

        }

        return maxString;

    }

    

    private String getPalindromeLen(int start, int end, String s){

        while(start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)){

            start--; 

            end++;

        }

        return s.substring(start+1, end);

    }

}