Longest Palindromic Substring

Difficulty: Medium | Acceptance: 36.30% | Paid: No

Topics: Two Pointers, String, Dynamic Programming

• Examples
• Constraints
• Brute Force Approach
• Expand Around Centers
• Dynamic Programming

Examples

Input

s = "babad"

Output

"bab"

Explanation

”aba” is also a valid answer.

Input

s = "cbbd"

Output

"bb"

Constraints

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

Brute Force Approach

Intuition

Check every possible substring to see if it’s a palindrome and keep track of the longest one found.

Steps

• Generate all possible substrings of the input string.
• For each substring, check if it is a palindrome.
• Keep track of the longest palindromic substring found so far.

def longestPalindrome(s: str) -> str:
    def is_palindrome(sub):
        return sub == sub[::-1]
    
    n = len(s)
    longest = ""
    
    for i in range(n):
        for j in range(i, n):
            substring = s[i:j+1]
            if is_palindrome(substring) and len(substring) > len(longest):
                longest = substring
    
    return longest

Complexity

• Time: O(n^3)
• Space: O(1)
• Notes: The time complexity is O(n^3) because we generate all O(n^2) substrings and check each one for palindrome property in O(n) time. Space complexity is O(1) as we only store a few variables.

Expand Around Centers

Intuition

A palindrome can be expanded from its center. We can iterate through all possible centers and expand around them to find the longest palindrome.

Steps

• Iterate through each character in the string as a potential center of a palindrome.
• For each center, expand outward in both directions as long as the characters match.
• Handle both odd-length palindromes (single character center) and even-length palindromes (between two characters).
• Keep track of the longest palindrome found during the expansion process.

def longestPalindrome(s: str) -> str:
    if not s:
        return ""
    
    start = 0
    max_len = 1
    
    def expand_around_center(left: int, right: int):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return right - left - 1
    
    for i in range(len(s)):
        len1 = expand_around_center(i, i)  # Odd length palindromes
        len2 = expand_around_center(i, i + 1)  # Even length palindromes
        current_max = max(len1, len2)
        
        if current_max > max_len:
            max_len = current_max
            start = i - (current_max - 1) // 2
    
    return s[start:start + max_len]

Complexity

• Time: O(n^2)
• Space: O(1)
• Notes: The time complexity is O(n^2) because we iterate through each character (n) and potentially expand to both ends (n in worst case). Space complexity is O(1) as we only use a few variables.

Dynamic Programming

Intuition

Use dynamic programming to store whether substrings are palindromes, building up from smaller substrings to larger ones.

Steps

• Create a 2D boolean array dp where dp[i][j] represents whether the substring from index i to j is a palindrome.
• Initialize the base cases: single characters are palindromes, and check for two-character palindromes.
• For substrings of length 3 and above, a substring s[i…j] is a palindrome if s[i] == s[j] and s[i+1…j-1] is a palindrome.
• Keep track of the longest palindromic substring found during the DP filling process.

def longestPalindrome(s: str) -> str:
    if not s:
        return ""
    
    n = len(s)
    # dp[i][j] will be True if substring s[i:j+1] is palindrome
    dp = [[False] * n for _ in range(n)]
    
    start = 0
    max_len = 1
    
    # All substrings of length 1 are palindromes
    for i in range(n):
        dp[i][i] = True
    
    # Check for substrings of length 2
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            start = i
            max_len = 2
    
    # Check for substrings of length 3 and more
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            
            # Check if s[i:j+1] is palindrome
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                
                if length > max_len:
                    start = i
                    max_len = length
    
    return s[start:start + max_len]

Complexity

• Time: O(n^2)
• Space: O(n^2)
• Notes: The time complexity is O(n^2) as we fill the 2D DP table. Space complexity is O(n^2) for storing the DP table. This approach trades space for time compared to the expand around centers approach.