algoadvance

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.

Clarifying Questions

  1. Input constraints?
    • The input string s will be of length at most 1000.
  2. Type of characters in the input string?
    • The input string s consists of lowercase English letters only.
  3. Example cases?
    • Example 1:
      • Input: s = "abc"
      • Output: 3 because a, b, and c are palindromic.
    • Example 2:
      • Input: s = "aaa"
      • Output: 6 because a, a, a, aa, aa, aaa are palindromic.

Strategy

We’ll use the “Expand Around Center” strategy. The idea is to consider each possible center for odd and even-length palindromes and attempt to expand outward as long as the substring remains a palindrome.

  1. Initialize a counter count to 0.
  2. Loop through each character in the string s, treating each character as the center of an odd-length palindrome.
  3. Expand from the center and count all valid palindromic substrings.
  4. Repeat the process for even-length palindromes by considering pairs of adjacent characters as the center.
  5. Count up all the palindromic substrings found and return the result.

Time Complexity

Since each center expansion takes O(N) time in the worst case, and there are 2N - 1 such centers (each character and space between characters), the overall time complexity is:

Code

Here’s the implementation of the strategy described:

def countSubstrings(s: str) -> int:
    def expand_around_center(left: int, right: int) -> int:
        count = 0
        while left >= 0 and right < len(s) and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
        return count

    count = 0
    for i in range(len(s)):
        # Count odd-length palindromic substrings
        count += expand_around_center(i, i)
        # Count even-length palindromic substrings
        count += expand_around_center(i, i + 1)
    
    return count

# Example Usage
print(countSubstrings("abc"))  # Output: 3
print(countSubstrings("aaa"))  # Output: 6

This solution efficiently counts the palindromic substrings using the expand-around-center approach, ensuring a thorough check of all possible palindromes within the given string s.

Try our interview co-pilot at AlgoAdvance.com