Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward. Substrings that occur multiple times are counted multiple times.

Function Signature:

def count_palindromic_substrings(s: str) -> int:
    """
    Count the number of palindromic substrings in the given string.

    Parameters:
    - s: A string.

    Returns:
    - int: The number of palindromic substrings.
    """
    # Your code here

Example:

s = "abc"
result = count_palindromic_substrings(s)
print(result)  # Output should be 3
# Explanation: The palindromic substrings are: "a", "b", "c".

s = "aaa"
result = count_palindromic_substrings(s)
print(result)  # Output should be 6
# Explanation: The palindromic substrings are: "a", "a", "a", "aa", "aa", "aaa".

s = "ababa"
result = count_palindromic_substrings(s)
print(result)  # Output should be 9
# Explanation: The palindromic substrings are: "a", "b", "a", "b", "a", "aba", "aba", "bab", "ababa".

s = ""
result = count_palindromic_substrings(s)
print(result)  # Output should be 0
# Explanation: An empty string contains no substring

s = "a"
result = count_palindromic_substrings(s)
print(result)  # Output should be 1
# Explanation: The only palindromic substring is: "a"

Note:

  • The input string s consists of lowercase English letters only.

Instructions:

  • Implement the count_palindromic_substrings function to solve the problem.
  • Use Python for your implementation.
  • Provide clear comments in your code to explain the logic.
  • Discuss the time and space complexity of your solution.

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