Longest Palindromic Substring

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

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

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 goal 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" Explanation: "aba" is also a valid answer.

**Example 2:**

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

## Naive (Brute Force) Solution

The simplest approach is to generate all possible substrings of the given string and check if each substring is a palindrome. We keep track of the longest palindromic substring found so far.

### Code (Python)

```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):
                if len(substring) > len(longest):
                    longest = substring
    return longest

Optimal Solution (Dynamic Programming)

We can use dynamic programming to solve this problem more efficiently. We create a 2D table dp where dp[i][j] is True if the substring s[i:j+1] is a palindrome, and False otherwise.

Algorithm

1. Initialize dp[i][i] = True for all i (single characters are palindromes).
2. Check for palindromes of length 2: dp[i][i+1] = (s[i] == s[i+1]).
3. For lengths k from 3 to n (length of s):
   • Iterate through all possible starting positions i.
   • Calculate the ending position j = i + k - 1.
   • dp[i][j] = (s[i] == s[j] and dp[i+1][j-1]).
4. Keep track of the start and end indices of the longest palindromic substring.

Code (Python)

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

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

    # 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

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

Big(O) Runtime Analysis

Brute Force:

• The brute-force solution has a time complexity of O(n^3), where n is the length of the string. This is because we generate O(n^2) substrings and each substring takes O(n) time to check for being a palindrome.

Dynamic Programming:

• The dynamic programming solution has a time complexity of O(n^2), where n is the length of the string. We fill in an n x n table.

Big(O) Space Usage Analysis

Brute Force:

• The brute-force solution has a space complexity of O(1), as we are only storing a few variables.

Dynamic Programming:

• The dynamic programming solution has a space complexity of O(n^2) because we use a 2D array dp of size n x n to store whether each substring is a palindrome.

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 has only one character, that character is the longest palindromic substring.
3. String with no palindromes: If the string has no palindromic substring of length greater than 1, the longest palindromic substring is any single character from the string.
4. Very long string: The solution should be efficient enough to handle strings up to the constraint length (1000).

These edge cases are handled correctly by the provided dynamic programming solution.