LC005 - Longest Palindromic Substring

Problem

Given a string s, return the longest palindromic substring in s

Example

Input: s = “babad”

Output: “bab”

Explanation: “aba” is also a valid answer

Solution

Naive

In the naive solution, we check every substring to see if it is a palindrome and take the longest one. This approach is $O(n^3)$ in time complexity.

def longestPalindrome(self, s: str) -> str:
	for length in range(len(s), 0, -1):
		for start in range(len(s) - length + 1):
			if self.check(s, start, start + length):
				return s[start : start + length]
	return ""

def check (self, s, i, j):
	lbound = i
	rbound = j - 1

	while lbound < rbound:
		if s[lbound] != s[rbound]:
			return False

		lbound += 1
		rbound -= 1
		
	return True

Improved

Intuitively, we can check whether or not a substring is a palindrome from its center, which is cheaper than checking it from its edges. We can iterate across the characters in the string array and expand outwards from each character to check whether or not it is a palindrome, and if so, how long it is. Time complexity of this approach will be $O(n^2)$, and we don't use extra space so space complexity is $O(1)$.

def longestPalindrome(self, s: str) -> str:
    ans = [0, 0]
    for i in range(len(s)):

        # expand for odd length palindromes
        odd = self.expand(s, i, i)
        if odd > ans[1] - ans[0] + 1:
            dist = odd // 2
            ans = [i - dist, i + dist]

        # expand for even length palindromes
        even = self.expand(s, i, i + 1)
        if even > ans[1] - ans[0] + 1:
            dist = (even // 2) - 1
            ans = [i - dist, i + 1 + dist]

    i, j = ans
    return s[i : j + 1]

def expand(self, s, i, j):
    lbound = i
    rbound = j

    # expand if bounds don't reach end
    while lbound >= 0 and rbound < len(s) and s[lbound] == s[rbound]:
        lbound -= 1
        rbound += 1

    # calculate length of palindrome from bounds
    return rbound - lbound - 1

Optimal

We can use Manacher’s algorithm to solve problems involving palindromes in $(O^n)$ time. However, this is usually beyond the scope of a normal interview.