Longest Palindromic Substring

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

For example:

Input: s = "babad" Output: "bab" or "aba"

Input: s = "cbbd" Output: "bb"

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

# Longest Palindromic Substring

## Problem Description

Given a string `s`, the task is to find and return the longest palindromic substring within `s`. A palindromic substring is a sequence of characters that reads the same forwards and backward. For example, "aba" and "madam" are palindromes.

**Example 1:**

Input: `s = "babad"`
Output: `"bab"` or `"aba"`

**Example 2:**

Input: `s = "cbbd"`
Output: `"bb"`

## Brute Force Approach

A naive approach would be to generate all possible substrings of the given string and check each substring for whether it is a palindrome. We keep track of the longest palindrome found so far.  This approach is simple to understand but not very efficient.

```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)):
            substring = s[i:j+1]
            if is_palindrome(substring) and len(substring) > len(longest):
                longest = substring
    return longest

# Example usage
s = "babad"
print(f"Brute force: Longest palindrome in '{s}' is '{longest_palindrome_brute_force(s)}'")

s = "cbbd"
print(f"Brute force: Longest palindrome in '{s}' is '{longest_palindrome_brute_force(s)}'")

Optimal Approach: Dynamic Programming

A more efficient approach involves dynamic programming. We create a 2D boolean array dp[i][j] where dp[i][j] is True if the substring s[i:j+1] is a palindrome, and False otherwise.

The base cases are:

• dp[i][i] = True for all i (a single character is always a palindrome).
• dp[i][i+1] = True if s[i] == s[i+1] (two adjacent equal characters form a palindrome).

For substrings of length 3 or more, dp[i][j] = True if s[i] == s[j] and dp[i+1][j-1] == True.

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

    # Base case: Single character palindromes
    for i in range(n):
        dp[i][i] = True

    # Base case: Two character palindromes
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            start = i
            max_len = 2

    # Check for palindromes of length 3 or more
    for k in range(3, n + 1):
        for i in range(n - k + 1):
            j = i + k - 1
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                if k > max_len:
                    start = i
                    max_len = k

    return s[start:start + max_len]

# Example usage
s = "babad"
print(f"DP: Longest palindrome in '{s}' is '{longest_palindrome_dp(s)}'")

s = "cbbd"
print(f"DP: Longest palindrome in '{s}' is '{longest_palindrome_dp(s)}'")

Big(O) Time Complexity Analysis

Brute Force

The brute force approach iterates through all possible substrings, which takes O(n^2) time. For each substring, it checks if it's a palindrome, which takes O(n) time. Therefore, the overall time complexity is O(n^3).

Dynamic Programming

The dynamic programming solution initializes a 2D array of size n x n, which takes O(n^2) space. It then iterates through the array to fill in the values, which also takes O(n^2) time. Therefore, the overall time complexity is O(n^2).

Big(O) Space Complexity Analysis

Brute Force

The brute force approach uses a constant amount of extra space, so the space complexity is O(1).

Dynamic Programming

The dynamic programming solution uses a 2D array of size n x n to store the palindrome information. Therefore, the space complexity is O(n^2).

Edge Cases

1. Empty String: If the input string is empty, the longest palindromic substring is an empty string.
2. Single Character String: If the input string contains only one character, that character is the longest palindromic substring.
3. String with No Palindromes: If the input string contains no palindromic substrings (e.g., "abcdefg"), the longest palindromic substring is a single character from the string.
4. Very Long Strings: For very long strings, the dynamic programming approach's O(n^2) space complexity could become a concern. In practice, the dynamic programming approach is typically more efficient due to avoiding redundant palindrome checks.

These edge cases are handled correctly in both the brute force and dynamic programming solutions.