Palindromic Substrings

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. A substring is a contiguous sequence of characters within the string.

For example:

Input: s = "abc" Output: 3 Explanation: Three palindromic strings: "a", "b", "c".

Input: s = "aaa" Output: 6 Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        count = 0
        
        # Helper function to expand around the center
        def expand_around_center(left, right):
            nonlocal count
            while left >= 0 and right < n and s[left] == s[right]:
                count += 1
                left -= 1
                right += 1
        
        # Iterate through each character in the string
        for i in range(n):
            # Odd length palindromes
            expand_around_center(i, i)
            
            # Even length palindromes
            expand_around_center(i, i + 1)
            
        return count

Explanation:

The problem asks us to find the number of palindromic substrings in a given string s. A palindrome is a string that reads the same forwards and backward. A substring is a contiguous sequence of characters within the string.

The provided Python code implements a solution using the "expand around center" approach. This approach efficiently counts all palindromic substrings by considering each character in the string as a potential center of a palindrome and expanding outwards.

1. Initialization:

   • n = len(s): Gets the length of the input string.
   • count = 0: Initializes a counter to store the number of palindromic substrings.

2. expand_around_center(left, right) function:

   • This helper function takes two indices, left and right, as input, representing the potential center of a palindrome.
   • It expands outwards from the center as long as the characters at the left and right indices are equal and the indices are within the bounds of the string.
   • For each valid palindrome found during the expansion, it increments the count.

3. Main loop:

   • The code iterates through each character in the string using a for loop: for i in range(n):
   • For each character, it considers two cases:
     • Odd length palindromes: It calls expand_around_center(i, i) to find palindromes with the current character as the center.
     • Even length palindromes: It calls expand_around_center(i, i + 1) to find palindromes with the current character and the next character as the center.

4. Return Value:

   • After iterating through all characters and expanding around each possible center, the function returns the final count, which represents the total number of palindromic substrings in the string.

Example:

For the input string s = "abc":

• The loop iterates three times (for 'a', 'b', and 'c').
• For 'a' (i=0), expand_around_center(0, 0) finds the palindrome "a".
• For 'b' (i=1), expand_around_center(1, 1) finds the palindrome "b".
• For 'c' (i=2), expand_around_center(2, 2) finds the palindrome "c".
• No even length palindromes are found.
• The function returns 3.

For the input string s = "aaa":

• The loop iterates three times (for each 'a').

• For the first 'a' (i=0):

  • expand_around_center(0, 0) finds "a".
  • expand_around_center(0, 1) finds "aa".

• For the second 'a' (i=1):

  • expand_around_center(1, 1) finds "a".
  • expand_around_center(1, 2) finds "aa".
  • expand_around_center(0,2) finds "aaa".

• For the third 'a' (i=2):

  • expand_around_center(2, 2) finds "a".

• The function returns 6.

Big O Runtime Analysis:

The time complexity of this solution is O(n^2), where n is the length of the string s.

The outer loop iterates through each character of the string once, which takes O(n) time.

For each character, the expand_around_center function expands outwards, potentially up to n/2 steps in each direction in the worst case (e.g., a string like "aaaaaa"). Therefore, the expand_around_center function takes O(n) time in the worst case.

Since the expand_around_center function is called for each character in the string, the overall time complexity is O(n * n) = O(n^2).

Big O Space Usage Analysis:

The space complexity of this solution is O(1), which means it uses a constant amount of extra space regardless of the input string size.

The solution uses a few variables (n, count, left, right, and i), but these variables take up a constant amount of space.

The expand_around_center function is called recursively, but the depth of the recursion is limited by the length of the string. However, this recursion is handled implicitly through the while loop, so it does not contribute to the space complexity.

Therefore, the overall space complexity is O(1).