4.23.6 — Palindromic Substrings

LeetCode 647 · Medium

The problem

Count how many substrings of s are palindromes. Substrings at different positions count separately even if they are identical.

"abc"   →  3     ("a", "b", "c")
"aaa"   →  6     ("a", "a", "a", "aa", "aa", "aaa")

Every single character is a palindrome, so the count is never below n.

The pattern

4.23.5 with a counter instead of a length comparison.

Expand from all 2n − 1 centres. Every successful expansion step is one more palindrome, because each step widens the current palindrome by one character on each side, producing a new, longer palindrome centred at the same place.

So you do not need to measure anything at the end — just count the iterations of the expansion loops.

The solution

PythonTypeScript

python

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

        def expand(lo: int, hi: int) -> int:
            count = 0
            while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
                count += 1                   # each successful step is a palindrome
                lo -= 1
                hi += 1
            return count

        for i in range(len(s)):
            total += expand(i, i)            # odd centres
            total += expand(i, i + 1)        # even centres

        return total

function countSubstrings(s: string): number {
  let total = 0;

  function expand(lo: number, hi: number): number {
    let count = 0;
    while (lo >= 0 && hi < s.length && s[lo] === s[hi]) {
      count++;
      lo--; hi++;
    }
    return count;
  }

  for (let i = 0; i < s.length; i++) {
    total += expand(i, i);
    total += expand(i, i + 1);
  }

  return total;
}

No off-by-one arithmetic at all, which makes this version cleaner than the "longest" one. You are counting iterations, not measuring a span, so the overshoot after the loop does not matter.

The odd expansion always counts at least 1 — a single character is a palindrome — so the total is automatically at least n.

The even expansion may count 0, when the two neighbouring characters differ.

Trace

"aaa"

centre	expansion	count
`(0,0)`	`a`	1
`(0,1)`	`aa`	1
`(1,1)`	`a`, then `aaa`	2
`(1,2)`	`aa`	1
`(2,2)`	`a`	1
`(2,3)`	out of bounds	0

Total 6 ✓ — three single characters, two "aa", one "aaa".

Complexity

$O(n^2)$ time, $O(1)$ space.

The DP version

Same table as 4.23.5, counting the True cells:

python

n = len(s)
dp = [[False] * n for _ in range(n)]
total = 0
for j in range(n):
    for i in range(j, -1, -1):                   # i counts DOWN
        if s[i] == s[j] and (j - i < 2 or dp[i+1][j-1]):
            dp[i][j] = True
            total += 1
return total

$O(n^2)$ time and $O(n^2)$ space. Same reasoning as before: centre expansion is better here, but the table is what you want when you will query many substrings, as in 4.18.7 Palindrome Partitioning.

Where this goes next

Longest Palindromic Substring — the same expansion, tracking the maximum. 4.23.5.
Count Different Palindromic Subsequences — much harder: subsequences allow gaps, and distinct means duplicates must be excluded, which needs careful 2-D DP.
Manacher's algorithm gives the count in $O(n)$ too, since the number of palindromes centred at a position is exactly its radius. 4.31.

What the interviewer will push on

"Why is every expansion step a new palindrome?" Each step produces a longer palindrome with the same centre, and different lengths are different substrings.

"How many centres?" 2n − 1, and be ready to justify the even ones.

"Do identical substrings at different positions count twice?" Yes — read the problem statement carefully. The distinct-substring version is a much harder problem.

"Can you do it in $O(n)$ ?" Manacher's, where the radius at each centre is the count.

One thing to volunteer: point out that this version avoids the off-by-one entirely, because counting iterations is simpler than measuring a span. Noticing when a small change makes code easier to get right is a good habit to show.

Next: 4.23.7 Decode Ways — back to the two-step recurrence, now with conditions on which steps are legal.

4.23.6 — Palindromic Substrings ​

The problem ​

The pattern ​

The solution ​

Trace ​

Complexity ​

The DP version ​

Where this goes next ​

What the interviewer will push on ​