Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. A palindromic substring is a substring that reads the same forwards and backward.

Write a function longestPalindrome(s) that takes a string s as input and returns the longest palindromic substring of s. If multiple palindromic substrings of the same maximum length exist, you may return any one of them.

Here are some examples to illustrate the problem:

• Example 1:

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

• Example 2:

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

• Example 3:

  • Input: s = "a"
  • Output: "a"

• Example 4:

  • Input: s = "ac"
  • Output: "a"

• Example 5:

  • Input: s = "racecar"
  • Output: "racecar"

Longest Palindromic Substring

Let's tackle the problem of finding the longest palindromic substring within a given string.

Naive (Brute Force) Solution

The most straightforward approach is to examine all possible substrings and check if each one is a palindrome. We can iterate through all possible starting positions and lengths of substrings.

1. Generate all substrings: Iterate through the string, creating all possible substrings.
2. Check for palindrome: For each substring, check if it's a palindrome by comparing it with its reverse.
3. Track the longest: Maintain a variable to store the longest palindromic substring found so far.

Code (Python):

python def longestPalindrome_bruteforce(s): longest = "" for i in range(len(s)): for j in range(i, len(s)): substring = s[i+1] if substring == substring[::-1]: if len(substring) > len(longest): longest = substring return longest

Big(O) Analysis:

• Time Complexity: O(n^3). Generating all substrings takes O(n^2), and checking if each substring is a palindrome takes O(n) time.
• Space Complexity: O(1). We only use a constant amount of extra space.

Optimal Solution (Dynamic Programming)

A more efficient solution uses dynamic programming. We can build a table dp where dp[i][j] is True if the substring s[i:j+1] is a palindrome, and False otherwise.

1. Base cases:
   • dp[i][i] = True (single characters are palindromes)
   • dp[i][i+1] = True if s[i] == s[i+1] (two adjacent characters are palindromes if they are equal)
2. Recursive relation: dp[i][j] = True if s[i] == s[j] and dp[i+1][j-1] == True
3. Track the longest: While filling the table, keep track of the start and end indices of the longest palindromic substring.

Code (Python):

python def longestPalindrome_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 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) Analysis:

• Time Complexity: O(n^2). We fill the dp table, which has size n x n, in O(1) time per cell.
• Space Complexity: O(n^2). We use an n x n table to store the intermediate palindrome results.

Optimal Solution (Expanding Around Center)

Another optimal solution involves expanding around the center. The idea is that a palindrome can be centered around a single character or between two characters. For each possible center, we expand outwards as long as the characters on both sides are equal.

1. Iterate through possible centers: The possible centers are the indices of the string, and also the spaces between the indices.
2. Expand outwards: For each center, expand outwards as long as s[left] == s[right].
3. Track the longest: Maintain a variable to store the longest palindromic substring found so far.

Code (Python):

python def longestPalindrome_expand(s): def expandAroundCenter(s, left, right): while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 return left + 1, right - 1

start = 0
end = 0

for i in range(len(s)):
    # Odd length palindrome
    left1, right1 = expandAroundCenter(s, i, i)
    # Even length palindrome
    left2, right2 = expandAroundCenter(s, i, i + 1)

    if (right1 - left1 + 1) > (end - start + 1):
        start = left1
        end = right1

    if (right2 - left2 + 1) > (end - start + 1):
        start = left2
        end = right2

return s[start:end + 1]

Big(O) Analysis:

• Time Complexity: O(n^2). For each of the n possible centers, we might expand outwards up to n times.
• Space Complexity: O(1). We only use a constant amount of extra space.

Edge Cases

• Empty string: If the input string is empty, the longest palindromic substring is an empty string.
• Single-character string: If the input string has only one character, that character is the longest palindromic substring.
• String with no palindromes: If the string has no palindromic substrings of length greater than 1, then the first character is the longest palindromic substring.

Conclusion

While the brute force solution is simple to understand, it's inefficient. The dynamic programming and expanding around the center approaches provide optimal O(n^2) time complexity for solving this problem. The expanding around center solution is generally preferred because it has O(1) space complexity compared to the DP solution's O(n^2) space complexity.