LeetCode 647 · Medium · 1-D Dynamic Programming

Palindromic Substrings

Count the contiguous pieces of s that read the same forward and backward. Pieces at different positions count separately, even when their text is equal.

O(n²)time
O(1)space
expandcount every match

lowercase letters · 1–12 characters

Palindromes found one chip per match, in the order the centres find them

public int countSubstrings(String s) { int res = 0; for (int i = 0; i < s.length(); i++) { res += countPali(s, i, i); // odd res += countPali(s, i, i + 1); // even } return res;} private int countPali(String s, int l, int r) { int res = 0; while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { res++; l--; r++; } return res;}
i
—
l, r
—
this centre
—
res
0

Why it works

  1. Brute force checks every substring: O(n²) of them, O(n) each to test, so O(n³).
  2. Each palindrome has exactly one centre, a character or the gap between two. Expanding from a centre finds its palindromes shortest first, and the first mismatch rules out every longer one. So each match is one new palindrome, never counted twice.
  3. 2n − 1 centres, at most n/2 expansions each: O(n²) time in the worst case (all one letter), O(1) space.
  4. Pitfall: skipping the even centres. "abba" has 6 palindromes, and "bb" and "abba" only show up from the gap between the two b's.
  5. Related: Longest Palindromic Substring runs the same loops but keeps the longest span instead of a count. The dp alternative fills dp[l][r] = s.charAt(l) == s.charAt(r) && dp[l+1][r−1] in O(n²) space.