TL;DR
Expand around each of the 2n-1 centers, counting every match: O(n²) time, O(1) space. A 2-D DP gives the same time in O(n²) space; Manacher reaches O(n).
Approach 1 — Brute force
Check every substring for the palindrome property and tally.
def countSubstrings(s: str) -> int:
n = len(s)
count = 0
for i in range(n):
for j in range(i, n):
sub = s[i:j + 1]
if sub == sub[::-1]:
count += 1
return count
Complexity: O(n²) substrings × O(n) reverse-compare = O(n³) time. At n = 1000 that’s 10⁹ — too slow.
Approach 2 — 2-D DP table
Define dp[i][j] = True iff s[i..j] is a palindrome, built from the shorter span inside it. Count every True.
Recurrence: dp[i][j] = (s[i] == s[j]) and (j - i < 2 or dp[i+1][j-1]).
flowchart TD
A["Check s[i..j]"] --> B{"s[i] == s[j]?"}
B -- no --> N["Not a palindrome"]
B -- yes --> C{"length <= 2 (j - i < 2)?"}
C -- yes --> P["Palindrome"]
C -- no --> D{"dp[i+1][j-1] true?"}
D -- yes --> P
D -- no --> N
Fill so the inner span dp[i+1][j-1] is ready first: iterate i from high to low, j from i upward.
def countSubstrings(s: str) -> int:
n = len(s)
dp = [[False] * n for _ in range(n)]
count = 0
for i in range(n - 1, -1, -1):
for j in range(i, n):
if s[i] == s[j] and (j - i < 2 or dp[i + 1][j - 1]):
dp[i][j] = True
count += 1
return count
Walkthrough (s = "aaa"): every diagonal (length 1) is True, giving 3. Length-2 spans [0,1] and [1,2] have equal chars, adding 2. Length-3 [0,2] has s[0]==s[2] and dp[1][1] True, adding 1. Total 6.
Complexity: O(n²) time, O(n²) space.
Approach 3 — Expand around center (space-optimized)
Each palindrome sits on one of 2n - 1 centers: n characters and n - 1 gaps. Expanding a center while the ends match discovers exactly one new palindrome per successful step, so you can count without any table.
def countSubstrings(s: str) -> int:
n = len(s)
def count_from(left: int, right: int) -> int:
c = 0
while left >= 0 and right < n and s[left] == s[right]:
c += 1
left -= 1
right += 1
return c
total = 0
for i in range(n):
total += count_from(i, i) # odd-length centers
total += count_from(i, i + 1) # even-length centers
return total
Walkthrough (s = "aba"): odd center i=0 gives "a" (1); odd center i=1 gives "b", then expands to "aba" since s[0]==s[2] (2); odd center i=2 gives "a" (1). Every even center fails (s[0]!=s[1], and so on). Total 1+2+1 = 4.
Complexity: O(n²) time, O(1) extra space.
Approach 4 — Manacher’s algorithm (O(n))
Manacher’s algorithm finds the palindrome radius r[i] at every center in linear time by reusing mirror information. The number of palindromes centered at position i of the transformed string is (r[i] + 1) // 2, and summing that over all centers gives the count directly.
def countSubstrings(s: str) -> int:
t = "#" + "#".join(s) + "#"
n = len(t)
radius = [0] * n
center = right = 0
for i in range(n):
if i < right:
radius[i] = min(right - i, radius[2 * center - i])
while (i - radius[i] - 1 >= 0 and i + radius[i] + 1 < n
and t[i - radius[i] - 1] == t[i + radius[i] + 1]):
radius[i] += 1
if i + radius[i] > right:
center, right = i, i + radius[i]
return sum((r + 1) // 2 for r in radius)
Complexity: O(n) time, O(n) space — asymptotically best, though expand-around-center is the usual expected answer.
Common pitfalls
- Only expanding odd centers and undercounting even palindromes like the
"aa"s in "aaa" — you need both (i, i) and (i, i+1).
- In the DP, iterating rows top-to-bottom reads
dp[i+1][j-1] before it exists; go bottom-up on i (or by increasing length).
- Counting distinct text instead of distinct positions —
"aaa" has only two distinct palindromic strings but six palindromic substrings.
- Forgetting the
j - i < 2 shortcut for length-1 and length-2 spans, which have no inner substring to consult.
Pattern takeaway
Counting palindromes reuses the exact same recurrence as finding the longest one (s[i]==s[j] and inside); you either sum the Trues of the 2-D table or, better, count expansions from each center. When a palindrome-DP question only asks for a count or a length, center-expansion usually beats the table on space while matching it on time.