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

Example:
Input: "babad"
Output: "bab"1 or "aba"

Solution:
This problem can be solved using a few different approaches, including:

Brute Force:

Generate all possible substrings.
Check if each substring is a palindrome.
Keep track of the longest palindrome found.
Time complexity: O(n^3)

Dynamic Programming:

Create a 2D boolean array dp where dp[i][j] is true if the substring s[i..j] is a palindrome.
Base cases:
dp[i][i] is true for all i (single characters are palindromes).
dp[i][i+1] is true if s[i] == s[i+1].
Recurrence relation:
dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]
Time complexity: O(n^2)

Manacher's Algorithm:

A more efficient algorithm specifically designed for finding the longest palindromic substring.
Uses a helper array to store the length of the longest palindrome centered at each position.

Time complexity: O(n)

Here is the python solution for above problem,

def longestPalindrome(s: str) -> str:
    n = len(s)
    if n <= 1:
        return s

    dp = [[False] * n for _ in range(n)]

    # 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):
        dp[i][i + 1] = (s[i] == s[i + 1])

    # Check for palindromes of length 3 and above
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]

    max_length = 0
    start = 0

    for i in range(n):
        for j in range(i, n):
            if dp[i][j] and j - i + 1 > max_length:
                max_length = j - i + 1
                start = i

    return s[start:start + max_length]