Longest Palindromic Substring

Problem

Find the longest palindromic substring within a string.

Input:  s = "babad"
Output: "bab"   (or "aba")

Python Solution

def longest_palindrome(s):
    def expand(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1:right]

    result = ""
    for i in range(len(s)):
        odd = expand(i, i)
        even = expand(i, i + 1)
        result = max(result, odd, even, key=len)
    return result

C++ Solution

string expand(string& s, int left, int right) {
    while (left >= 0 && right < s.size() && s[left] == s[right]) {
        left--; right++;
    }
    return s.substr(left + 1, right - left - 1);
}

string longestPalindrome(string s) {
    string result = "";
    for (int i = 0; i < s.size(); i++) {
        string odd = expand(s, i, i);
        string even = expand(s, i, i + 1);
        if (odd.size() > result.size()) result = odd;
        if (even.size() > result.size()) result = even;
    }
    return result;
}

Java Solution

class Solution {
    public String longestPalindrome(String s) {
        String result = "";
        for (int i = 0; i < s.length(); i++) {
            String odd = expand(s, i, i);
            String even = expand(s, i, i + 1);
            if (odd.length() > result.length()) result = odd;
            if (even.length() > result.length()) result = even;
        }
        return result;
    }

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

Complexity

Time: O(n²) — for each of the n possible centres (odd and even), expansion can take up to O(n) in the worst case. Space: O(1) extra, aside from the returned substring.