Solution 1: Brute Force

Intuition:

In a brute-force approach, we would generate all possible substrings and check if each substring is a palindrome. We would then count the number of palindromic substrings.

Here’s how the brute-force approach would work:

  1. Generate all possible substrings of s.
  2. Check if each substring is a palindrome by iterating from the start and end of the substring and comparing characters.
  3. If a substring is a palindrome, increment the count.
  4. Return the final count as the number of palindromic substrings.

Although this approach is straightforward, it is highly inefficient, especially for longer strings, as it involves checking a large number of substrings.

Solution:

def count_palindromic_substrings(s: str) -> int:

    # Define a helper function to check if a given substring is 
    # a palindrome by comparing it with its reverse
    def is_palindrome(substring: str) -> bool:
        return substring == substring[::-1]
    
    # Initialize a variable count to keep track of the number 
    # of palindromic substrings
    count = 0
    
    # Generate all possible substrings and check if each one is a palindrome
    n = len(s)
    for i in range(n):
        for j in range(i + 1, n + 1):

            # For each substring, check if it is a palindrome
            if is_palindrome(s[i:j]):
                count += 1  # If it is, we increment the count
    
    return count

# Test cases
s = "abc"
result = count_palindromic_substrings(s)
print(result)  # Output should be 3

s = "aaa"
result = count_palindromic_substrings(s)
print(result)  # Output should be 6

s = "ababa"
result = count_palindromic_substrings(s)
print(result)  # Output should be 9

s = ""
result = count_palindromic_substrings(s)
print(result)  # Output should be 0

s = "a"
result = count_palindromic_substrings(s)
print(result)  # Output should be 1

Time Complexity:

  • Generating all possible substrings requires nested loops that iterate over the string s.
    • The outer loop runs n times, where n is the length of the input string s.
    • The inner loop runs n - i times for each iteration of the outer loop.
    • For each iteration, checking if a substring is a palindrome takes O(m) time, where m is the length of the substring. In the worst case, the length of the substring can be n, resulting in O(n) time complexity for each iteration.
  • Therefore, the overall time complexity of the brute-force approach is O(n^3)

Space Complexity:

  • The space complexity of the brute-force approach is O(1) because it only uses a constant amount of additional space for variables and does not store any additional data structures proportional to the input size. Therefore, the space complexity is constant.

Solution 2: Dynamic Programming

Intuition:

To count the number of palindromic substrings in the given string, we can use dynamic programming. We’ll create a 2D boolean array dp, where dp[i][j] will be True if the substring from index i to index j is a palindrome, and False otherwise.

We can initialize dp[i][i] to True for all i since single characters are palindromes by definition. Then, for substrings of length 2, we’ll check if the characters at both ends are the same.

Next, we’ll iterate over all substring lengths greater than 2. For each length len, we’ll consider all substrings of that length and check if the characters at both ends are the same and if the substring inside is a palindrome. If both conditions are met, we’ll mark dp[i][j] as True.

Finally, we’ll count the number of True values in the dp array to find the total number of palindromic substrings.

Solution:

def count_palindromic_substrings(s: str) -> int:

    # Initialize a 2D boolean array dp of size n x n, where n is the length of the input string s.
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    count = 0
    
    # Initialize dp[i][i] to True for single characters
    for i in range(n):
        dp[i][i] = True
        count += 1
    
    # Check for palindromes of length 2
    # by comparing characters at adjacent positions
    # and mark them as palindromes (set to True) if they are equal
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            count += 1

    # Check for palindromes of length greater than 2
    # check if the characters at both ends are equal 
    # and if the substring inside is a palindrome (using values from dp)
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                count += 1
    
    return count

# Test cases
s = "abc"
result = count_palindromic_substrings(s)
print(result)  # Output should be 3

s = "aaa"
result = count_palindromic_substrings(s)
print(result)  # Output should be 6

s = "ababa"
result = count_palindromic_substrings(s)
print(result)  # Output should be 9

s = ""
result = count_palindromic_substrings(s)
print(result)  # Output should be 0

s = "a"
result = count_palindromic_substrings(s)
print(result)  # Output should be 1

Time Complexity:

  • The time complexity of this approach is O(n^2), where n is the length of the input string s.
  • We iterate over all substrings of length 1, 2, and greater than 2, which takes O(n^2) time.

Space Complexity:

  • The space complexity is O(n^2) as we use a 2D array of size n x n to store the boolean values representing whether substrings are palindromes or not.

Solution 3: Expansion Around the Center

Intuition:

There is another approach to solve this problem using expansion around the center technique. The idea is to treat each character in the string s as a potential center of a palindrome and expand outwards to check if it forms a palindrome.

There are two cases to consider:

  • For odd-length palindromes: We consider each character s[i] as the center and expand both left and right as long as the characters at the left and right positions are equal.
  • For even-length palindromes: We consider the interval between s[i] and s[i+1] as the center and expand both left and right until the characters at the left and right positions are equal.

Solution:

def count_palindromic_substrings(s: str) -> int:
    count = 0
    
    # Function to expand around the center and count palindromes
    def expand_around_center(left: int, right: int) -> int:
        nonlocal count
        while left >= 0 and right < len(s) and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
    
    # Iterate over each character as potential center for odd-length palindromes
    for i in range(len(s)):
        expand_around_center(i, i)
    
    # Iterate over each interval between characters as potential center for even-length palindromes
    for i in range(len(s) - 1):
        expand_around_center(i, i + 1)
    
    return count

# Test cases
s = "abc"
result = count_palindromic_substrings(s)
print(result)  # Output should be 3

s = "aaa"
result = count_palindromic_substrings(s)
print(result)  # Output should be 6

s = "ababa"
result = count_palindromic_substrings(s)
print(result)  # Output should be 9

s = ""
result = count_palindromic_substrings(s)
print(result)  # Output should be 0

s = "a"
result = count_palindromic_substrings(s)
print(result)  # Output should be 1

Time Complexity:

  • We iterate over each character in the string s and treat it as the potential center of an odd-length palindrome. This process takes O(n) time, where n is the length of the input string s.
    • For each character, we perform an expansion outward to check if it forms a palindrome. This expansion process takes O(n) time in the worst case. Consider a scenario where all characters in the string are the same, leading to the maximum possible number of palindromic substrings.
  • Additionally, we iterate over each interval i and i + 1 in the string s and treat it as the potential center of an even-length palindrome. Again, this process takes O(n) time.
    • The expansion outward also takes O(n).
  • Therefore, the overall time complexity of the expansion around the center technique is O(n^2), where n is the length of the input string s.

Space Complexity:

  • The space complexity is O(1) as we use only a constant amount of additional space for variables.