Longest Palindromic Substring

Problem: Longest Palindromic Substring

We can start stretching out a palindromic string from each character and update our answer.

Code in Python:

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        ans, ans_len = "", 0
        n = len(s)
        for i in xrange(n):
            j = 0
            while i-j >= 0 and i+j < n and s[i-j] == s[i+j]: j += 1
            if 2*j-1 > ans_len: ans, ans_len = s[i-j+1:i+j], 2*j-1
            j = 0
            while i-j >= 0 and i+j+1 < n and s[i-j] == s[i+j+1]: j += 1
            if 2*j > ans_len: ans, ans_len = s[i-j+1:i+j+1], 2*j
        return ans

Code in Java:

public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) return s;
        String result = s.substring(0, 1);
        for (int i = 0; i < s.length(); i++) {
            if (s.length()-i < result.length()/2) break;
            String oddLength = twoWaySearch(s, i, i);
            if (result.length() < oddLength.length()) result = oddLength;
            String evenLength = twoWaySearch(s, i, i+1);
            if (result.length() < evenLength.length()) result = evenLength;
        }
        return result;
    }

    private String twoWaySearch(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--; r++;
        }
        return s.substring(l+1, r);
    }
}