LeetCode Solutions Blog

Palindromic Substrings

Number: 647

Difficulty: Medium

Paid? No

Problem Description

Given a string s, count and return the number of palindromic substrings found in s. A palindrome reads the same backward as forward, and every single character is considered a palindrome by itself.

Key Insights

Every individual character is a palindrome.
Palindromes can be expanded from a center point; centers can be single characters (odd length) or between two characters (even length).
The "expand around center" technique efficiently counts palindromes in O(n^2) time.
Dynamic programming could also be used but requires extra space and is more complex to implement.

Space and Time Complexity

Time Complexity: O(n^2) where n is the length of the string. Space Complexity: O(1) if using the expand-around-center method (ignoring recursion/stack overhead).

Solution

The solution employs the expand-around-center approach:

Iterate over each index of the string considering it as the center of a palindrome.
For each center, expand in both directions (left and right) as long as the characters are the same and within bounds.
Count every valid palindrome found during the expansion.
Repeat for both odd-length centers (a single index) and even-length centers (between two indices).

This method efficiently checks all potential palindromic substrings without extra space for dynamic programming tables.

Code Solutions

# Define a function to count palindromic substrings in a string
def countSubstrings(s: str) -> int:
    # Initialize the result variable to accumulate count of palindromic substrings
    result = 0

    # Helper function that expands around a center (left, right) and counts palindromes
    def expandAroundCenter(left: int, right: int) -> int:
        count = 0
        # Expand as long as indices are within bounds and characters at left and right are equal
        while left >= 0 and right < len(s) and s[left] == s[right]:
            # Found a palindrome, so increment count 
            count += 1
            left -= 1  # Move left pointer outward
            right += 1 # Move right pointer outward
        return count

    # Iterate over each character in the string
    for i in range(len(s)):
        # Count odd-length palindromes (center is i)
        result += expandAroundCenter(i, i)
        # Count even-length palindromes (center is between i and i+1)
        result += expandAroundCenter(i, i + 1)

    return result

# Example usage:
# result = countSubstrings("aaa")
# print(result)