5. Longest Palindromic Substring

Question

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

1. A string is called a palindrome string if the reverse of that string is the same as the original string

Example 1

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

Example 2

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

Solution 1: Brute Force (TLE)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        ans = s[0]
        n = len(s)
        for i in range(n - 1):
            for j in range(i + 1, n):
                subS = s[i: j + 1]
                if self.isPalindrome(subS):
                    if len(subS) > len(ans):
                        ans = subS
        return ans
    
    
    def isPalindrome(self, subStr: str) -> bool:
        return subStr == subStr[::-1]

Time Complexity: O(N^3)
Space Complexity: O(N)

Solution 2: Dynamic Program

TODO

Time Complexity: O(N^2)
Space Complexity: O(N^2)

Solution 3: Double Pointer

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        ans = ""
        ansLen = 0
        
        for i in range(n):
            # Odd Len, expand from center
            lft, rht = i, i
            while lft >= 0 and rht < n and s[lft] == s[rht]:
                if (rht - lft + 1) > ansLen:
                    ans = s[lft: rht + 1]
                    ansLen = (rht - lft + 1)
                lft -= 1
                rht += 1
            
            # Even Len, start from both side
            lft, rht = i, i + 1
            while lft >= 0 and rht < n and s[lft] == s[rht]:
                if (rht - lft + 1) > ansLen:
                    ans = s[lft: rht + 1]
                    ansLen = (rht - lft + 1)
                lft -= 1
                rht += 1
            
        return ans

Time Complexity: O(N^2)
Space Complexity: O(1)

Reference

https://www.youtube.com/watch?v=XYQecbcd6_c

Follow-up: 516. Longest Palindromic Subsequence

Given a string s , find the length of the longest substring t that contains at most 2 distinct characters

TODO

Time Complexity: O()
Space Complexity: O()

Follow-up: 9. Palindrome Number

Given an integer x, return true if x is palindrome integer

1. An integer is a palindrome when it reads the same backward as forward. For example, 121 is palindrome while 123 is not

TODO

Time Complexity: O()
Space Complexity: O()