Longest Palindromic Substring

Naive Approach: Brute Force

The most straightforward approach is to generate all possible substrings of the given string s and check if each substring is a palindrome. We keep track of the longest palindromic substring found so far and update it whenever we encounter a longer one.

Algorithm

1. Iterate through all possible starting positions i of substrings in s.
2. For each starting position i, iterate through all possible ending positions j (where j >= i) to generate substrings s[i...j].
3. For each substring s[i...j], check if it is a palindrome.
4. If s[i...j] is a palindrome and its length is greater than the length of the current longest palindrome, update the longest palindrome.
5. Return the longest palindrome found.

Code (Python)

def is_palindrome(s):
    return s == s[::-1]

def longest_palindrome_brute_force(s):
    longest = ""
    for i in range(len(s)):
        for j in range(i, len(s)):
            sub = s[i:j+1]
            if is_palindrome(sub) and len(sub) > len(longest):
                longest = sub
    return longest

Complexity Analysis

• Time Complexity: O(n^3), where n is the length of the string s. This is because we have two nested loops to generate all possible substrings (O(n^2)), and for each substring, we need to check if it is a palindrome (O(n)).
• Space Complexity: O(1), as we are only using a constant amount of extra space.

Optimal Approach: Dynamic Programming

We can use dynamic programming to solve this problem more efficiently. Let dp[i][j] be a boolean value indicating whether the substring s[i...j] is a palindrome. We can define dp[i][j] recursively as follows:

• dp[i][i] = True for all i (a single character is always a palindrome).
• dp[i][i+1] = (s[i] == s[i+1]) for all i (two adjacent characters form a palindrome if they are equal).
• dp[i][j] = (s[i] == s[j] and dp[i+1][j-1]) for j > i+1 (a substring s[i...j] is a palindrome if its first and last characters are equal and the substring s[i+1...j-1] is also a palindrome).

Algorithm

1. Initialize a 2D boolean array dp of size n x n to store the palindrome information, where n is the length of the string s.
2. Initialize the base cases: dp[i][i] = True for all i, and dp[i][i+1] = (s[i] == s[i+1]) for all i.
3. Iterate through the possible lengths of palindromic substrings, starting from length 3. We will iterate with increasing length.
4. For each length, iterate through all possible starting positions i of substrings of that length.
5. Calculate the ending position j of the substring as j = i + length - 1.
6. If s[i] == s[j] and dp[i+1][j-1] is true, then dp[i][j] = True. Also update the longest palindrome string if necessary.
7. Return the longest palindrome found.

Code (Python)

def longest_palindrome_dp(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    start = 0
    max_len = 1

    for i in range(n):
        dp[i][i] = True

    for i in range(n - 1):
        if s[i] == s[i+1]:
            dp[i][i+1] = True
            start = i
            max_len = 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
                if length > max_len:
                    start = i
                    max_len = length

    return s[start:start + max_len]

Complexity Analysis

• Time Complexity: O(n^2), where n is the length of the string s. This is because we have two nested loops to fill the dp array.
• Space Complexity: O(n^2), as we are using a 2D array of size n x n to store the palindrome information.

Edge Cases

• Empty string: If the input string s is empty, the longest palindromic substring is an empty string. The code needs to handle this case. The DP solution will return an empty string if the input is also an empty string.
• Single-character string: If the input string s contains only one character, that character is the longest palindromic substring. The DP solution covers this case.
• String with no palindromes: If the input string s contains no palindromes (e.g., "abcd"), the longest palindromic substring is the first character of the string. The DP solution covers this case too.
• String with all same characters: If the input string s consists of only one distinct character repeated multiple times, then the longest palindromic substring is the entire input string. The DP solution covers this case as well.