LeetCode 647: Palindromic Substrings — Step-by-Step Visual Trace

#leetcode #python #algorithms

Medium — String | Two Pointers | Expand Around Centers | Palindrome

The Problem

Count the total number of palindromic substrings in a given string, where a palindromic substring reads the same forwards and backwards.

Approach

Use the expand around centers technique by checking every possible center position in the string. For each position, expand outward while characters match to count palindromes of both odd and even lengths.

Time: O(n²) · Space: O(1)

Code

class Solution:
    def countSubstrings(self, s: str) -> int:
        def expandAroundCenter(left: int, right: int) -> int:
            count = 0
            # Expand around the center while the characters at both ends are equal.
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
                count += 1
            return count

        if not s:
            return 0

        total_palindromes = 0

        for i in range(len(s)):
            # Check for odd-length palindromes.
            total_palindromes += expandAroundCenter(i, i)

            # Check for even-length palindromes.
            total_palindromes += expandAroundCenter(i, i + 1)

        return total_palindromes