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

Source: Dev.to

Problem Description

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.

Complexity

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

Solution

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