We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Palindromic Substrings

Difficulty: Medium

Problem Description

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.

Key Insights

  • Each character in the string can be considered a center of a palindrome.
  • Palindromes can be of odd or even lengths, which requires checking from each character and between each pair of characters.
  • Use a two-pointer approach to expand around potential centers to count palindromic substrings efficiently.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(1)

Solution

To solve the problem, we can use a two-pointer approach to expand around each character and each pair of characters in the string. For each center, we check for palindromes by comparing characters outward while they match. We increment a count for each valid palindrome found. This approach ensures that all possible substrings are checked without explicitly generating them.

Code Solutions

def countSubstrings(s: str) -> int:
    count = 0
    
    # Helper function to expand around the center
    def expand_around_center(left: int, right: int) -> None:
        nonlocal count
        while left >= 0 and right < len(s) and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
    
    for i in range(len(s)):
        # Odd length palindromes
        expand_around_center(i, i)
        # Even length palindromes
        expand_around_center(i, i + 1)
    
    return count
← Back to All Questions