Problem Solving Question | Find the Longest Palindromic Substring

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 the 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]

No feedback provided.