Solution 1

This problem evaluates the your ability to work with strings, dynamic programming, and problem-solving skills related to palindrome identification.

Below is a Python implementation of the longest_palindromic_substring function to find the longest palindromic substring in a given string:

def longest_palindromic_substring(s: str) -> str:
    if not s:
        return ""

    start, end = 0, 0

    # Iterate through each character in the string
    for i in range(len(s)):
        # Check for palindromes with odd length
        len1 = expand_around_center(s, i, i)

        # Check for palindromes with even length
        len2 = expand_around_center(s, i, i + 1)

        # Find the maximum palindrome length
        max_len = max(len1, len2)

        # Update the start and end indices if a longer palindrome is found
        if max_len > end - start:
            start = i - (max_len - 1) // 2
            end = i + max_len // 2

    # Return the longest palindromic substring
    return s[start:end + 1]

def expand_around_center(s: str, left: int, right: int) -> int:
    """
    Helper function to find the length of a palindrome by expanding around the center.

    Parameters:
    - s: Input string.
    - left: Left index.
    - right: Right index.

    Returns:
    - int: Length of the palindrome.
    """
    # Expand around the center while characters match
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1

    # Return the length of the palindrome
    return right - left - 1

# Example usage:
input_str1 = "babad"
result1 = longest_palindromic_substring(input_str1)
print(result1)  # Output: "bab" or "aba"

input_str2 = "cbbd"
result2 = longest_palindromic_substring(input_str2)
print(result2)  # Output: "bb"

This solution uses the “expand around center” approach, where each character and the space between two characters are treated as potential centers for palindromes.

Time Complexity:

The time complexity of the longest_palindromic_substring function is O(n^2), where n is the length of the input string s. The dominant factor in this time complexity arises from the nested loop structure.

Here’s a breakdown of the main components contributing to the time complexity:

  1. Outer Loop (for i in range(len(s))): This loop iterates through each character in the input string, and for each character, the expand_around_center function is called. Therefore, the overall time complexity contributed by the outer loop is O(n).

  2. Inner Loop (while left >= 0 and right < len(s) and s[left] == s[right] within expand_around_center): This loop expands around the center (or centers, in the case of even-length palindromes) of the potential palindrome. In the worst case, this loop can expand up to O(n/2) times, where n is the length of the input string. This is because the palindrome can extend from the center to either end of the string. However, since the expand operation takes constant time for each iteration, the overall time complexity contributed by the inner loop is O(n).

Therefore, the overall time complexity is the product of the outer and inner loop complexities, giving O(n) * O(n) = O(n^2), where n is the length of the input string.

Space Complexity:

The space complexity of the provided solution is O(1). This is because the amount of additional memory used by the algorithm remains constant, regardless of the size of the input string. The primary reason for this constant space complexity is the absence of any data structures or arrays that scale with the input size.

Solution 2: Dynamic Programming

There are multiple approaches to solving the Longest Palindromic Substring problem. Another common approach is using dynamic programming to build a table that represents whether a substring is a palindrome or not.

Here’s an example implementation using dynamic programming:

def longest_palindromic_substring(s: str) -> str:
    n = len(s)
    if n == 0:
        return ""

    # Create a table to store whether a substring is a palindrome
    dp = [[False] * n for _ in range(n)]

    # All substrings of length 1 are palindromes
    for i in range(n):
        dp[i][i] = True

    start, max_len = 0, 1

    # Check substrings of length 2
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            start = i
            max_len = 2

    # Check substrings of length 3 or more
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1

            # Check if the substring is a palindrome
            if dp[i + 1][j - 1] and s[i] == s[j]:
                dp[i][j] = True
                start = i
                max_len = length

    return s[start:start + max_len]

# Example usage:
input_str1 = "babad"
result1 = longest_palindromic_substring(input_str1)
print(result1)  # Output: "bab" or "aba"

input_str2 = "cbbd"
result2 = longest_palindromic_substring(input_str2)
print(result2)  # Output: "bb"

Time Complexity:

Let’s break down the time complexity of the dynamic programming solution for finding the longest palindromic substring:

  1. Initialization (O(n)):
    • We initialize a table dp of size n by n, where n is the length of the input string s.
    • We iterate over each character in the string (for i in range(n)) and mark single-character substrings as palindromes.
  2. Checking Length-2 Palindromes (O(n)):
    • We iterate over the string (for i in range(n-1)) and check pairs of adjacent characters to identify palindromes of length 2.
    • If a pair is a palindrome, we mark it as such in the table.
  3. Checking Length-3 or More Palindromes (O(n^2)):
    • We use a nested loop (for length in range(3, n + 1): and for i in range(n - length + 1):) to iterate over all substrings of length 3 or more.
    • For each substring, we check whether it is a palindrome based on the information stored in the table for shorter substrings.
    • The total number of iterations in this part is proportional to the sum of the lengths of all substrings, which is O(n^2) in the worst case.

The overall time complexity is dominated by the checking of length-3 or more palindromes, making it O(n^2). The initialization and checking of length-2 palindromes contribute linearly to the overall time complexity but are asymptotically less significant.

In summary, the time complexity is O(n^2), where n is the length of the input string s.

Space Commplexity:

The space complexity of this solution is O(n^2) due to the 2D matrix dp, which has a size of n by n, where n represents the length of the input string s.