[LeetCode] 5. Longest Palindromic Substring

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

Since every individual character is a valid palindrome.  We may loop the string and expand the left and right boundary of each character to find the longest palindrome centered by this character.

Time Complexity :  O(len(s) * len(s))
Space Complexity :  O( len(s) ),  for space used by the tmp substrings

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """

        L = len(s)

        def palindrome(left, right):
            while left >= 0 and right < L:
                if s[left] != s[right]:
                    break

                left -= 1
                right += 1

            return s[left+1: right]

        result = ""

        i = 0
        while i < L:
            tmp = palindrome(i-1, i+1)
            if len(result) < len(tmp):
                result = tmp

            if i + 1 < L and s[i] == s[i+1]:
                tmp = palindrome(i-1, i+2)
                if len(result) < len(tmp):
                    result = tmp

            i += 1

        return result

This problem has optimal substructure.

Let dp[i+1][j-1] = True when substring s[i+1:j-1] is a palindrome.
Then substring s[i: j+1] is palindrome when s[i] == s[j] and dp[i+1][j-1] = True.
Or substring s[i: j+1] is palindrome when s[i] == s[j] and j - i == 1 which means s[i] is conjuct with s[j].

Greedy approach does not apply to this problem. Because if we only record the longest palindrome ends by s[i] which is s[j] ... s[i],  there could be a s[k] ( k > j ) can make a longer palindrome s[k] ... s[i]s[i+1]. But s[k] .. s[i] is a shorter palindrome than s[j] .. s[i].  ( i.e.  s = "aaaa" ).

Time Complexity = O(len(s) * len(s))
Space Complexity = O(1)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        N = len(s)
        
        # dp[left][right] = True if s[left:right+1] is palindrome
        dp = [[False] * N for _ in range(N)]
        
        resultStart = 0
        resultLen = 1
        
        for i in range(N):
            dp[i][i] = True
        
        # iterate backward because dp[left][right] depends on dp[left+1][right-1]
        for left in reversed(range(N)):
            for right in range(left+1, N):
                if s[left] == s[right]:
                    if right - left == 1 or dp[left+1][right-1]:
                        dp[left][right] = True
                
                        if right - left + 1 > resultLen:
                            resultLen = right - left + 1
                            resultStart = left
        
        return s[resultStart:resultStart + resultLen]

The equivalent Java solution:

class Solution {
    public String longestPalindrome(String s) {
        int N = s.length();
        boolean [][] dp = new boolean[N][N];
        
        int maxLen = 1;
        int left = N-1;
        
        for (int l = N-1; l >= 0; l--) {
            for (int r = N-1; r >= l; r--) {
                // s[l:r] is a palindrome is s[l] == s[r] and s[l+1:r-1] is a palindrome
                dp[l][r] = s.charAt(l) == s.charAt(r) && (r - l <= 1 || dp[l+1][r-1]);
                if (dp[l][r] && r - l + 1 > maxLen) {
                    maxLen = r - l + 1;
                    left = l;
                }
            }
        }
        
        return s.substring(left, left + maxLen);
    }
}

Use hash table to trim unnecessary comparings.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        
        @lru_cache(maxsize = None)
        def isPalindrom(left, right):
            return left >= right or s[left] == s[right] and isPalindrom(left+1, right-1)
        
        
        N = len(s)
        if N <= 1: return s
        
        result = ""
        seen = defaultdict(list)
        
        for left in reversed(range(N)):
            seen[s[left]].append(left)
            
            for right in seen[s[left]]:
                if isPalindrom(left, right) and right - left + 1 > len(result):
                    result = s[left:right+1]
                    break
     
        return result

Use BFS approach to expand from center.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        queue = deque()
        
        N = len(s)
        if N <= 1: return s
        
        result = (0, 0)
        resultLen = 1
        
        for i in range(N):
            queue.append((i,i))
            
            if i + 1 < N and s[i] == s[i+1]:
                queue.append((i, i+1))
        
        while queue:
            left, right = queue.popleft()
            if right - left + 1 > resultLen:
                result = (left, right)
                resultLen = right - left + 1

            if left - 1 >= 0 and right + 1 < N and s[left-1] == s[right+1]:
                queue.append((left-1, right+1))
        
        left, right = result
        return s[left: right+1]

Edited on 11/21/2021. Add the Java solution.