🟨 Palindromic Substrings (#647)

🔗 Problem Link

• LeetCode - Palindromic Substrings
• NeetCode - Palindromic Substrings

📋 Problem Statement

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.

💡 Examples

Example 1

Input: s = "abc"
Output: 3
Explanation: "a", "b", "c"

Example 2

Input: s = "aaa"
Output: 6
Explanation: "a", "a", "a", "aa", "aa", "aaa"

🔑 Key Insights & Approach

Core Observation: Expand around each possible center and count palindromes.

Why Expand Around Center?

• O(n²) time, O(1) space
• Count while expanding
• Simple and efficient

Pattern: "Expand Around Center" for counting palindromes.

🐍 Solution: Python

Approach: Expand Around Center

Time Complexity: O(n²) | Space Complexity: O(1)

class Solution:
    def countSubstrings(self, s: str) -> int:
        count = 0

        def expand_around_center(left, right):
            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)):
            expand_around_center(i, i)      # Odd length
            expand_around_center(i, i + 1)  # Even length

        return count

🔵 Solution: Golang

Approach: Expand Around Center

Time Complexity: O(n²) | Space Complexity: O(1)

func countSubstrings(s string) int {
    count := 0

    expandAroundCenter := func(left, right int) {
        for left >= 0 && right < len(s) && s[left] == s[right] {
            count++
            left--
            right++
        }
    }

    for i := 0; i < len(s); i++ {
        expandAroundCenter(i, i)
        expandAroundCenter(i, i+1)
    }

    return count
}

📚 References

• NeetCode - Palindromic Substrings