💬 Discord
Sign In
NeetCode #667LC-647Medium1-D Dynamic ProgrammingBlind 75NC 150NC 250
← Back to All Problems

#667 · #647 · Palindromic Substrings(回文子串)

📌 Problem Statement & Constraints

Given a string s, return the number of palindromic substrings in it. Substrings with different start or end indices are counted separately even if they are identical. Constraints: 1 <= s.length <= 1000, and s consists of lowercase English letters.

💡 Core Algorithmic Approaches

  1. Expand around each of the 2n - 1 centers, exactly as in the longest-palindrome problem.
  2. Every successful expansion corresponds to one palindromic substring, so increment a counter inside the expansion loop.
  3. Sum the counts over all odd and even centers.
  4. The structure mirrors problem 5; only the bookkeeping changes from tracking a maximum to accumulating a total.

💻 Benchmark Python3 Implementation

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

        def expand(l: int, r: int) -> int:
            cnt = 0
            while l >= 0 and r < len(s) and s[l] == s[r]:
                cnt += 1
                l -= 1
                r += 1
            return cnt

        for i in range(len(s)):
            total += expand(i, i)       # odd-length centers
            total += expand(i, i + 1)   # even-length centers
        return total

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n^2): each center expands up to n steps.
💾 Space Complexity
O(1): a counter and two pointers.

⚠️ Interview Pitfalls & Follow-ups

  • Counting distinct palindromic strings instead of occurrences: aaa has 6 palindromic substrings, not 1.
  • Only counting odd-length centers: even-length palindromes must be counted through the between-character centers.
  • Counting each palindrome twice: the odd and even calls cover disjoint parity classes, so there is no double counting.
  • Breaking on the first mismatch without counting: each matching pair is itself a palindrome, so the increment belongs inside the loop.