Given a string text, the objective is to locate longest contiguous substring that reads the same forward and backward.

Constraints:

• 1 <= text.length <= 1000
• text consists of alphanumeric English characters only.

Dynamic Programming Approahc

1. State Definition Define a 2D table is_palindrome[i][j] where i and j are indices. The value is True if the substring text[i:j+1] is a palindrome, otherwise False.

2. Transition Formula A substring text[i...j] is a palindrome if:

• The characters at the ends match (text[i] == text[j]).
• The inner substring text[i+1...j-1] is also a palindrome (or the length is small enough that the inner part is trivially valid).

Specifically:

• If j - i < 3 (length is 2 or 3) and text[i] == text[j], it is a palindrome.
• Otherwise, is_palindrome[i][j] = is_palindrome[i+1][j-1].

3. Initialization Every single character is a palindrome:

length = len(text)
matrix = [[False] * length for _ in range(length)]
for idx in range(length):
    matrix[idx][idx] = True

4. Traversal Order Iterate by increasing substring length L. For each length, slide the window across the string to evaluate left boundaries i and calculate right boundaries j.

5. Implementation

class Solution:
    def longestPalindrome(self, text: str) -> str:
        n = len(text)
        if n < 2:
            return text
        
        best_start, max_size = 0, 1
        dp = [[False] * n for _ in range(n)]
        
        # Initialize single characters
        for k in range(n):
            dp[k][k] = True
            
        # Check substrings of increasing length
        for width in range(2, n + 1):
            for left in range(n):
                right = left + width - 1
                
                if right >= n:
                    break
                    
                if text[left] == text[right]:
                    if right - left < 3:
                        dp[left][right] = True
                    else:
                        dp[left][right] = dp[left + 1][right - 1]
                        
                if dp[left][right] and width > max_size:
                    max_size = width
                    best_start = left
                    
        return text[best_start:best_start + max_size]

Complexity Analysis:

• Time: $O(n^2)$ due to the nested loops over substring lengths and starting positions.
• Space: $O(n^2)$ for storing the DP matrix.