algoadvance

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

Clarifying Questions

  1. Input Constraints:
    • What is the maximum length of the string s?
    • Can the string be empty?
  2. Output Specifications:
    • If there are multiple palindromic substrings with the maximum length, should we return the first one that appears?
  3. Additional Details:
    • Are there any special characters, or is the input strictly alphanumeric?
    • Should the solution be case-sensitive?

Code

def longest_palindrome(s: str) -> str:
    n = len(s)
    if n == 0:
        return ""
    
    # Table to store the palindrome status
    dp = [[False] * n for _ in range(n)]
    
    # Variables to track the start and end of the longest palindrome
    start, max_length = 0, 1
    
    # Every single character is a palindrome
    for i in range(n):
        dp[i][i] = True
    
    # Check for palindromes of length 2
    for i in range(n-1):
        if s[i] == s[i+1]:
            dp[i][i+1] = True
            start = i
            max_length = 2
    
    # Check for lengths greater than 2
    for length in range(3, n+1):  # length is the current substring length
        for i in range(n - length + 1):
            j = i + length - 1  # Ending index of the current substring
            if s[i] == s[j] and dp[i+1][j-1]:
                dp[i][j] = True
                if length > max_length:
                    start = i
                    max_length = length
    
    return s[start:start + max_length]

# Example usage
s = "babad"
print(longest_palindrome(s))  # Output: "bab" or "aba"

Strategy

  1. Dynamic Programming Approach:
    • We will use a 2D DP table where dp[i][j] will be True if the substring s[i:j+1] is a palindrome.
    • Initialize the table such that each single character is a palindrome (dp[i][i] = True).
  2. Check Substrings:
    • Check for substrings of length 2. If s[i] == s[i+1], then mark dp[i][i+1] = True.
  3. General Case for Substrings Longer Than 2:
    • For substrings longer than 2 characters, check if the ends are equal (i.e., s[i] == s[j]) and whether the substring excluding the ends is a palindrome (i.e., dp[i+1][j-1]).
  4. Update Longest Palindrome:
    • Track the starting index and the length of the longest palindrome found during the iteration.

Time Complexity

This solution efficiently finds the longest palindromic substring by balancing between space and time complexity, and ensures correctness via the dynamic programming approach.

Try our interview co-pilot at AlgoAdvance.com