Leetcode 5: Longest Palindromic Substring

By /

The original question can be found here.

There’re multiple solutions to this question, and we’ll start with the brute force one.

Brute Force

We enumerate all substrings and check if it’s palindromic. If yes, we update the final result by keeping track of the length and starting position.

class Solution {
    public String longestPalindrome(String s) {
        // sanity check
        if (s == null || s.length() == 0) {
            return "";
        }

        int startPosition = -1, longestLength = -1;
        // enumarate starting position
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                if (isPalindrome(s, i, j)) {
                    if (j - i + 1 > longestLength) {
                        startPosition = i;
                        longestLength = j - i + 1;
                    }
                }
            }
        }

        // return result
        return s.substring(startPosition, startPosition + longestLength);
    }

    private boolean isPalindrome(String s, int left, int right) {
        while (right > left && s.charAt(left) == s.charAt(right)) {
            left++;
            right--;
        }
        return left >= right;
    }
}

Time complexity: O(n^3). Space complexity: O(1)

We can optimize this solution a little bit by enumerating the length of substring from n to 1. Once we found a palindromic substring, we immediately return it without further looping since we know there will be no more substrings that have longer length. Here is the Python code:

class Solution:
    def longestPalindrome(self, s: str) -> str:
        for length in range(len(s), 0, -1):
            for left in range(len(s) - length + 1):
                if self.is_palindrome(s, left, left + length - 1):
                    return s[left: left + length]
    
    def is_palindrome(self, s, left, right):
        while left < right and s[left] == s[right]:
            left += 1
            right -= 1
        return left >= right

While we optimize a little bit, the time complexity is still O(n^3).

Center Enumeration

This solution is a little bit like greedy algorithm because we enumerate the center of palindrome substring and extend to both ends as far as we can get. If it’s odd length, we start with a single letter and expand. If it’s even length, we start with 2 adjacent letters and expand.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return s
        ans = (0, 0)
        for mid in range(len(s)):
            ans = max(ans, self.expand_palindrome(s, mid, mid))
            ans = max(ans, self.expand_palindrome(s, mid, mid + 1))
        return s[ans[1]: ans[0] + ans[1]]
        
    def expand_palindrome(self, s: str, left: int, right: int) -> (int, int):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return right - left - 1, left + 1

Here in our little helper method, we return a tuple with first element as length of palindrome substring, second element as the starting position. Time complexity: O(n^2). Space Complexity: O(1).

Dynamic Programming

We can use dynamic programming to solve this problem as well. The transition formula is as follwing: is_palindrome[i][j] = is_palindrome[i + 1][j - 1] && s[i] == s[j], where is_palindrome[i][j] stands for whether the substring starting at index i, and ending at index j(inclusive) is palindromic or not.

One trick for Python developer here is how we instantiate the 2 dimensional array. [False] * n will create an 1-d array with n False values in it: [False, False, ..., False], and let’s assign this newly created array to variable a. But why don’t we create the 2-d array by [a] * n again? The reason is array a will be shallow copied because a is a refernce now, and we’ll create an 2-d array with each array actually the same array in memory. So if we change matrix[0][0] to True, matrix[1][0] and matrix[2][0] will be True as well.

So what does [[False] * n for _ in range(n)] mean? It means, execute [False] * n by n times, which will give us a n * n 2d array. What’s the underscore in for _ in range(n) mean? That means we don’t need the loop counter here, so usually we mark it as _.

In dynamic programming, one important thing to do is to initialize the state matrix. In this problem, the base case is for a string with 1 letter, it’s considerred as palindromic, thus is_palindrome[i][i] = True. What does is_palindrome[i][i - 1] = True mean? Let’s say we compute is_palindrome[2][3], since is_palindrome[i][j] = is_palindrome[i + 1][j - 1] and s[i] == s[j], we need to know the value of is_palindrome[3][2], so we need is_palindrome[i][i - 1] = True, and can be considered as for an empty string, it’s also palindromic.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return s
        
        n = len(s)
        is_palindrome = [[False] * n for _ in range(n)]
        for i in range(len(s)):
            is_palindrome[i][i] = True
        for i in range(1, len(s)):
            is_palindrome[i][i - 1] = True

        ans = s[0]
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                is_palindrome[i][j] = is_palindrome[i + 1][j - 1] and s[i] == s[j]
                if is_palindrome[i][j] and length > len(ans):
                    ans = s[i:j + 1]
        
        return ans

Time complexity: O(n^2). Space complexity: O(n^2).

Scroll to Top