Hard Problemspalindromecountinginterval

Palindromic Substring Count

Given a string, count how many of its contiguous substrings read the same forwards and backwards. Identical characters appearing at different positions are counted as separate substrings.

Do this lesson first: longest common subsequence

Example input

s = "abaab"

Expected output

8

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[i][j] is 1 if the stretch s[i..j], both ends included, is a palindrome and 0 if it is not. Two numbers name the stretch, so the table is the upper triangle, i <= j, of a square. That flag is not the answer: the question counts palindromes over EVERY stretch, so the answer is the number of 1s in the whole triangle. total[i], in the extra last column, is the count of palindromes that start at position i or later, and total[0] is the answer.

dp[i][j] = 0 if s[i] != s[j], 1 if s[i] = s[j] and j = i + 1, otherwise dp[i + 1][j - 1]; total[i] = dp[i][i] + ... + dp[i][n - 1] + total[i + 1], and the answer is total[0]

Look at the two end characters, s[i] and s[j], the move the LCS lesson derives at /courses/dynamic-programming/longest-common-subsequence and longest-palindromic-subsequence applies to one string. Here there is no choice to make. A palindrome's first and last characters are equal, so differing ends settle it: 0. If they match, they mirror each other and can never be what spoils the stretch, so it is a palindrome exactly when the stretch strictly inside is one, and the cell copies dp[i + 1][j - 1]. There is no max, as there is on the subsequence page, because a substring cannot drop an end: the stretch is fixed, and the only question is yes or no. The count is not a decision at any one cell. It is a sum over the whole triangle, and the total column is where that sum is built: row i's flags are the palindromes that start at i, and total[i + 1] already counts the ones that start later.

dp[i][i] = 1 on the diagonal: one character is a palindrome. Two kinds of cell are set without reading anything: a stretch whose ends differ is 0, and a length-2 stretch whose ends match, like 'aa' at dp[2][3], is 1, because its inside, dp[i + 1][i], would sit below the diagonal and is not a stretch at all. A longer stretch with matching ends reads the one cell diagonally below-left of it, a shorter stretch, so filling by length makes it final in time. The total column exists because the count is a sum over the table, and a sum needs a cell to land in; no flag cell can hold it. Strictly, total[i] needs only its own row, which is final once the stretches of length n - i are done, plus total[i + 1]; filling the column after the whole triangle, from the bottom up, is simply the order that is always safe: total[n - 1] is the last row's lone flag, a base, and each total[i] then reads its own row and the total just below it.

Tabulation over n(n + 1) / 2 stretches with constant work at each, plus n totals that between them read every flag once, so O(n²) time and O(n²) space. At 5 characters that is 15 triangle cells, 5 bases and 10 computes, of which 7 read nothing and 3 copy their inside, and then the total column's 1 base and 4 computes. The snippet keeps the total column to match the grid, but in practice it collapses to one running counter, count += dp[i][j], added as each flag is written; the page gives it a column only so that the sum has somewhere to appear. Memoization gains nothing, because every stretch is counted and so every cell is needed.

Time O(n²)Space O(n²)

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

dp[i][i] = 1 on the diagonal: one character is a palindrome. Two kinds of cell are set without reading anything: a stretch whose ends differ is 0, and a length-2 stretch whose ends match, like 'aa' at dp[2][3], is 1, because its inside, dp[i + 1][i], would sit below the diagonal and is not a stretch at all. A longer stretch with matching ends reads the one cell diagonally below-left of it, a shorter stretch, so filling by length makes it final in time. The total column exists because the count is a sum over the table, and a sum needs a cell to land in; no flag cell can hold it. Strictly, total[i] needs only its own row, which is final once the stretches of length n - i are done, plus total[i + 1]; filling the column after the whole triangle, from the bottom up, is simply the order that is always safe: total[n - 1] is the last row's lone flag, a base, and each total[i] then reads its own row and the total just below it.

Rows ↓
Cols →

0 a

1 b

2 a

3 a

4 b

total

0 a

1

0

1

0

8

1 b

·

1

0

1

6

2 a

·

1

0

4

3 a

·

1

0

2

4 b

·

1

Rows ↓row i: where the stretch of the string starts

Cols →column j: where it ends, so the cell is 1 when s[i..j] is a palindrome and 0 when not; the last column, total, counts the palindromes that start at row i or any row below it

palindromic-substring-count.ts

1function countPalindromicSubstrings(s) {
2 const n = s.length;
3 const dp = Array.from({ length: n }, () => new Array(n).fill(0));
4 for (let i = 0; i < n; i++) dp[i][i] = 1;
5 for (let len = 2; len <= n; len++) {
6 for (let i = 0; i + len - 1 < n; i++) {
7 const j = i + len - 1;
8 dp[i][j] = s[i] !== s[j] ? 0 : len === 2 ? 1 : dp[i + 1][j - 1];
9 }
10 }
11 const total = new Array(n + 1).fill(0);
12 for (let i = n - 1; i >= 0; i--) {
13 total[i] = total[i + 1];
14 for (let j = i; j < n; j++) total[i] += dp[i][j];
15 }
16 return total[0];
17}

Base caseComputedBeing readAnswer

The code, the trap, the variations

palindromic-substring-count.ts

1function countPalindromicSubstrings(s) {
2 const n = s.length;
3 const dp = Array.from({ length: n }, () => new Array(n).fill(0));
4 for (let i = 0; i < n; i++) dp[i][i] = 1;
5 for (let len = 2; len <= n; len++) {
6 for (let i = 0; i + len - 1 < n; i++) {
7 const j = i + len - 1;
8 dp[i][j] = s[i] !== s[j] ? 0 : len === 2 ? 1 : dp[i + 1][j - 1];
9 }
10 }
11 const total = new Array(n + 1).fill(0);
12 for (let i = n - 1; i >= 0; i--) {
13 total[i] = total[i + 1];
14 for (let j = i; j < n; j++) total[i] += dp[i][j];
15 }
16 return total[0];
17}

Where people go wrong

Writing the matched-ends case as one line, dp[i][j] = dp[i + 1][j - 1], with no special case for length 2. For a pair of neighbours, dp[i + 1][j - 1] is dp[i + 1][i], below the diagonal; a zero-filled array returns 0 there instead of failing, so every pair of equal neighbours is marked NOT a palindrome. The error then spreads outward: on 'abaab' it loses 'aa' and with it 'baab', which wraps 'aa', and counts 6 instead of 8. Measured on this page's string, it is wrong at every slider size from 4 characters up, 13 instead of 15 at 9, and right only at 2 and 3, where the string has no equal neighbours to lose. Either set a length-2 stretch with matching ends to 1 directly, as this page does, or initialise the cells below the diagonal to 1, the empty stretch counting as a palindrome.

Count DISTINCT palindromic substrings, so a repeated 'a' counts once.
The flag table does not change; only what is done with it does. The total column cannot answer this, because it adds positions, so collect the substring of every flagged stretch into a set and report its size instead. On 'abaab' that is 5, namely 'a', 'b', 'aa', 'aba' and 'baab', where this page counts 8. A set of strings costs more than a sum, so for long inputs a palindromic tree (eertree) is the usual tool.
Find the longest palindromic substring instead of counting them.
The same flag table, filled the same way; the total column is replaced by tracking the longest stretch flagged 1. On 'abaab' that is 'baab', length 4. Compare longest-palindromic-subsequence, which may skip characters: there differing ends can drop either end and the cell becomes a max, while here a stretch cannot drop anything, so the cell stays a yes-or-no flag.
Expand around each centre instead of building a table.
The fact used is the same, a palindrome with matching ends around a palindromic inside, but it is applied outward: from each of the 2n - 1 centres (each character and each gap between neighbours), grow both ends while they match, and count one palindrome per step. On 'abaab' it finds the same 8. The table and the total column both disappear, so space drops to O(1), and time stays O(n²) in the worst case. Manacher's algorithm reuses the mirror image of earlier expansions to get it down to O(n).
Use the flag table to split a string into the fewest palindromic pieces.
palindrome-partitioning checks each piece directly on the string. Handing it this table instead turns every check into one lookup, and over prefixes it brings that page's work down to O(n²). The table itself is built exactly as here; only its consumer changes.

Palindrome Partitioning Word Wrap Problem