Given a string, find the longest palindromic substring in it. A palindrome is a word, phrase, or sequence that reads the same backward as forward. A substring is a contiguous sequence of characters within the string.

Function Signature:

def longest_palindromic_substring(s: str) -> str:
    """
    Find the longest palindromic substring in the given string.

    Parameters:
    - s: Input string.

    Returns:
    - str: Longest palindromic substring.
    """
    # Your code here

Example:

# Input: "babad"
# Output: "bab" or "aba" (either one is acceptable)

# Input: "cbbd"
# Output: "bb"

Note:

  • A palindromic substring may be of even or odd length.
  • You may assume that the maximum length of the given string is 1000.

Instructions:

  • Write the longest_palindromic_substring function to solve the problem.
  • Implement your solution in Python.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊