Longest Palindrome - Leetcode Solution

The problem is to find the longest palindrome substring in a given string.

Solution:

One way to solve this problem is to use a dynamic programming approach. We can create a 2D boolean array dp[l][r], where dp[l][r] is true if the substring from index l to index r in the string s is a palindrome. The base cases are when l=r and l=r+1.

The recurrence relation is:

• dp[l][r] = true if dp[l+1][r-1] is true and s[l] = s[r]
• dp[l][r] = false if s[l] != s[r]

We can initialize the dp array with all false values and then fill it in from the bottom up and left to right.

Algorithm:

1. Initialize a 2D boolean array dp with size n*n where n is the length of the input string s.
2. Initialize all diagonal elements dp[i][i] and dp[i][i+1] (i.e., substrings of length 1 and 2) as true.
3. Traverse the input string s starting from length 3 and iterate over all possible substrings of length i from j, where dp[j][j+i-1] is true if s[j] = s[j+i-1] and dp[j+1][j+i-2] is true.
4. Update longest_palindrome if the length of the current substring (i.e., j+i-1-j+1) is greater than the current longest_palindrome.
5. Return longest_palindrome.

Time Complexity: O(n^2)

Let's implement the above algorithm:

Python Code:

class Solution: def longestPalindrome(self, s: str) -> str: n = len(s) dp = [[False for j in range(n)] for i in range(n)]

    longest_palindrome = ""
    for i in range(n):
        dp[i][i] = True
        longest_palindrome = s[i]
    
    for i in range(n-1):
        if s[i] == s[i+1]:
            dp[i][i+1] = True
            longest_palindrome = s[i:i+2]
    
    for i in range(3, n+1):
        for j in range(n-i+1):
            k = j + i - 1
            if s[j] == s[k] and dp[j+1][k-1]:
                dp[j][k] = True
                if i > len(longest_palindrome):
                    longest_palindrome = s[j:k+1]
    
    return longest_palindrome

Input:

s = "babad"

Output:

"bab"

Explanation:

The longest palindromic substring in "babad" is "bab".

1