LeetCode 5. Longest Palindromic Substring

Description

https://leetcode.com/problems/longest-palindromic-substring/description/

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

Explanation

A palindromic string meets two criteria:

1. first and the last character are the same
2. the inner word between the first and the last character is a palindromic string

The basic idea is to use dynamic programming to determine whether a substring is palindromic string base on above criteria.

Need to be careful that when returning the result, the end index need to plus 1, because java substring method doesn’t include the ending index.

Java Solution

class Solution {
    public String longestPalindrome(String s) {        
        if (s == null || s.length() < 2) {
            return s;
        }

        int length = s.length();
        
        boolean[][] isPalindrome = new boolean[length][length];
        
        int left = 0;
        int right = 0;
        
        for (int j = 1; j < length; j++) {
            for (int i = 0; i < j; i++) {
                boolean isInnerWordPalindrome = isPalindrome[i + 1][j - 1] || j - i <= 2;
                
                if (s.charAt(i) == s.charAt(j) && isInnerWordPalindrome) {
                    isPalindrome[i][j] = true;
                    
                    if (j - i > right - left) {
                        left = i;
                        right = j;
                    }
                }                
            }            
        }
        
        return s.substring(left, right + 1);
        
        // Time Complexity: O(n ^ 2)
        // Space Complexity: O(n ^ 2)
    }
}

Python Solution

class Solution:
    def longestPalindrome(self, s: str) -> str:        
        if not s:
            return ""
        
        longest = ""
        for middle in range(len(s)):
            sub = self.find_palindrome_from(s, middle, middle)
            if len(sub) > len(longest):
                longest = sub
            
            sub = self.find_palindrome_from(s, middle, middle + 1)
            if len(sub) > len(longest):
                longest = sub
                
        return longest
        
    def find_palindrome_from(self, string, left, right):
        while left >= 0 and right < len(string):
            if string[left] != string[right]:
                break
            left -= 1
            right += 1
            
        return string[left + 1:right]        

• Time complexity: O(N^2).
• Space complexity: O(S).