Longest Palindromic Substring

Lecture 77 :- Longest Palindromic Substring

Finding the longest palindromic substring is a classic problem in computer science and can be solved efficiently using dynamic programming. A palindromic substring is a substring that reads the same forwards and backward.

To find the longest palindromic substring, you can use the following approach:

Initialize a 2-dimensional boolean array to keep track of whether substrings are palindromes. Let dp[i][j] be True if the substring from index i to j is a palindrome, otherwise False.

For each character s[i], dp[i][i] is always True since a single character is always a palindrome.

For each character s[i] and s[i+1], if s[i] == s[i+1], then dp[i][i+1] is True as they form a palindrome.

For substrings of length greater than 2 (i.e., len > 2), you can use the recursive formula:

cssCopy code

dp[i][j] = dp[i+1][j-1] and s[i] == s[j]

Keep track of the longest palindromic substring while calculating the dp array.

Here's a Python function that implements the algorithm:

pythonCopy code

def longest_palindromic_substring(s):    n = len(s)    dp = [[False] * n for _ in range(n)]    start, max_length = 0, 1    # All substrings of length 1 are palindromes    for i in range(n):        dp[i][i] = True    # Check for substrings 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 substrings of length greater than 2    for length in range(3, n + 1):        for i in range(n - length + 1):            j = i + length - 1            if s[i] == s[j] and dp[i + 1][j - 1]:                dp[i][j] = True                start = i                max_length = length    return s[start:start + max_length] # Example usage: s = "babad" result = longest_palindromic_substring(s) print(result)

Output:

sqlCopy code

"bab" or "aba" (both are valid solutions)

The function will return the longest palindromic substring of the input string s. In the example provided, both "bab" and "aba" are valid solutions, and the function can return either of them.