0005. Longest Palindromic String

Problem

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

Examples

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Constraints:

1 <= s.length <= 1000
s consist of only digits and English letters.

Analysis

Solution

# Solution 1: dynamic programming O(n^2) - brute force: traverse all characters and substrings twice
def solution(s):
    n = len(s)
    dp = [[False]*n]*n # define an array to store the palindromic status between i and j
    if n<2:
        return s
    res = s[0]
    for j in range(1,n):
        for i in range(j):
            # s[i:j] is palindromic if str [i+1:j-1] is palindromic and s[i] = s[j]
            dp[i][j] = s[i] == s[j] and (j-i<3 or dp[i+1][j-1])
            if dp[i][j] and (res == "" or j-i+1 > len(res)):
                res = s[i:j+1]
    return res

s = "babad"
print(solution(s))

s = "cbbd"
print(solution(s))

s = "a"
print(solution(s))

s = "ac"
print(solution(s))

s = "aa"
print(solution(s))

bab
bb
a
a
aa

# solution 2: determine the palindromic status from the center.
# traverse the string, and assume the current character is the center of palindromic string and move the left and right pointer one step until the longest palidromic string
# 
def solution(s):
    n = len(s)
    if n<2:
        return s 
    res = []

    def palindrome(s, i, j):
        """find the palindrome starting from i and j
            - i = j, for odd string
            - i = j - 1, for even string
        """
        while i >= 0 and j < len(s) and s[i] == s[j]:
                i -= 1
                j += 1

        return s[i+1:j]
        
    res = ""
    for i in range(n):
        # find odd palindrome
        ps = palindrome(s, i, i) 
        res = ps if len(ps) > len(res) else res 

        # find even palindrome
        ps = palindrome(s, i, i+1)
        res = ps if len(ps) > len(res) else res 

    return res

s = "babad"
print(solution(s))

s = "cbbd"
print(solution(s))

s = "a"
print(solution(s))

s = "ac"
print(solution(s))

s = "aa"
print(solution(s))

bab
bb
a
a
aa