This problem can be solved using two approaches:

  1. Dynamic Programming Time Complexity: O(n²) Space Complexity: O(n²)

  2. Two-Pointer (Expand Around Center) Time Complexity: O(n²) Space Complexity: O(1)

Approach I: Dynamic Programming

In this approach, we aim to check all substrings of the string. Specifically, we will check substrings of lengths 1, 2, 3, …, up to len(s).

We use a 2D array dp of size n x n where n is the length of the string. The rows represent the starting index, and the columns represent the length of the substring. For example, dp[5][7] represents the substring starting at index 5 with a length of 7.

For dp[i][length] to be True, the following conditions need to be satisfied:

  1. The first and last characters of the substring must be the same (s[i] == s[i + length]).
  2. The middle substring (between the first and last characters) must also be a palindrome (dp[i+1][length-2]).

Base Cases:

  1. All single-character substrings are palindromes:
    for i in range(len(s)):
    dp[i][0] = True
    count[0] += 1
 # Check for two-character palindromes:
 for i in range(len(s) - 1):
     if s[i] == s[i+1]:
         dp[i][1] = True
         count[0] += 1

Explanation of DP Filling

When computing dp[i][length], where length represents the length of the substring we are evaluating, we follow these conditions:

  1. First Condition: The first and last characters of the substring must be the same. This is checked using:
    s[i] == s[i + length]

This condition ensures that the characters at the starting index i and the index i + length are identical.

  1. Second Condition: The middle substring (the portion of the substring that excludes the first and last characters) must also be a palindrome. This is checked with:
    dp[i + 1][length - 2]

Here, i + 1 is the starting index of the middle substring, and length - 2 represents its length. If this condition is True, it indicates that the substring formed by excluding the first and last characters is also a palindrome.

Thus, for dp[i][length] to be True, both conditions must be satisfied. If they are, we can increment our count of palindromic substrings

Base Case Code

The base cases for the DP table are established as follows:

  1. Single-Character Substrings: All single-character substrings are palindromes. This is represented in the DP table by setting dp[i][0] to True for all valid indices i. We also increment the count of palindromic substrings.

    def baseCasesForDP(self, dp: list[list[bool]], s: str, count: list[int]) -> None:
    for i in range(len(s)):
        dp[i][0] = True
        count[0] += 1

     for i in range(len(s) - 1):
         if s[i] == s[i+1]:
             dp[i][1] = True
             count[0] += 1

DP Initialization

We initialize the dp array and a count list to track the number of palindromes: ```python # Variable initialization rows = len(s) cols = len(s) count = [0] # List to store the count (as integers are immutable in Python)

# DP Initialization
dp = []
for i in range(rows):
    t = [False] * cols
    dp.append(t)

Filling the DP Table

We then fill the DP table for substrings of length 3 and above:

length = 2
for length in range(2, len(s)):
    for i in range(len(s) - length):
        if s[i] == s[i + length] and dp[i + 1][length - 2] == True:
            dp[i][length] = True
            count[0] += 1

## Full Code