Naive Approach - Brute Force

The most straightforward approach is to generate all possible substrings of the input string and then check each substring to see if it's a palindrome. We keep track of the longest palindromic substring found so far and update it whenever we find a longer one.

def longestPalindrome_brute_force(s: str) -> str:
    n = len(s)
    longest = ""
    
    for i in range(n):
        for j in range(i, n):
            substring = s[i:j+1]
            if substring == substring[::-1]:  # Check if palindrome
                if len(substring) > len(longest):
                    longest = substring
    
    return longest

Time Complexity: O(n^3). We have two nested loops that iterate through all possible substrings (O(n^2)), and for each substring, we check if it's a palindrome in O(n) time.

Space Complexity: O(1). We only use a constant amount of extra space.

This approach is simple to understand, but it's not very efficient.

Optimal Approach - Dynamic Programming

A more efficient approach is to use dynamic programming. We create a 2D table dp where dp[i][j] is True if the substring s[i:j+1] is a palindrome, and False otherwise.

We can fill this table diagonally. A single character is always a palindrome. Two characters are a palindrome if they are equal. For substrings of length 3 or more, s[i:j+1] is a palindrome if s[i] == s[j] and s[i+1:j] is a palindrome (i.e., dp[i+1][j-1] is True).

def longestPalindrome_dp(s: str) -> str:
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    start = 0
    max_len = 1
    
    # Single characters are palindromes
    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_len = 2
    
    # Check for palindromes of length 3 or more
    for k in range(3, n + 1):
        for i in range(n - k + 1):
            j = i + k - 1
            if s[i] == s[j] and dp[i+1][j-1]:
                dp[i][j] = True
                if k > max_len:
                    start = i
                    max_len = k
    
    return s[start:start + max_len]

Time Complexity: O(n^2). We fill the dp table which is of size n x n.

Space Complexity: O(n^2). We use a 2D array dp of size n x n to store the palindrome information.

Edge Cases

• Empty string: If the input string is empty, the longest palindromic substring is an empty string.
• Single-character string: If the input string has only one character, that character itself is the longest palindromic substring.
• String with no palindromes: If the input string has no palindromic substring of length greater than 1, then the longest palindromic substring will be a single character.