Blind 75 Visualized

#54 · 1D DP

Palindromic Substrings

Given a string s, return the number of palindromic substrings in it. Substrings with different positions count separately even if they have the same letters.

MediumLeetCode
  • Computing
  • Depends on
  • Answer
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Substring table dp[i][j]

dp[i][j] is true when s[i..j] is a palindrome. It depends on the two end letters and the inner substring, so every substring is decided from shorter ones. The answer is the number of true cells.

Memory layout

An n × n boolean grid (upper triangle used).

OperationCost
timeO(n²)
spaceO(n²)

Centres and radii

A palindrome is fixed by its centre and its half-length, so counting palindromes is counting, for each of the 2n − 1 centres, how far it can expand. The number of palindromes at a centre equals the number of successful expansion steps.

Memory layout

A counter; Manacher adds one radius per position.

OperationCost
expand all centresO(n²) worst case; O(n) with Manacher

Why it fits

  • Every palindromic substring has exactly one centre, so summing the expansion counts over all centres counts each palindrome once and none twice.
  • If a palindrome extends to a certain radius, all smaller radii at the same centre are palindromes too, so a centre's radius is also its count.
  • The structure "inside a palindrome is a palindrome" lets a table (or the mirror trick) reuse smaller answers instead of re-testing.

Why alternatives degrade

Counting distinct palindromes with a set:
The problem counts occurrences by position, so "a" at index 0 and "a" at index 2 count twice; a set of strings would merge them.
Sorting letters:
Palindromes depend on order, which sorting destroys.
Testing each substring from scratch:
It repeats the inner comparisons and costs O(n³).

Four approaches, from naive to production

1 · beginner

Test every substring

time O(n³)space O(1)

For every pair (i, j) test whether s[i..j] reads the same both ways by comparing from the ends inwards, and count the successes.

int countSubstrings(string s) {
    auto isPal = [&](int l, int r) -> bool {
        while (l < r) {
            if (s[l] != s[r]) return false;
            l++;
            r--;
        }
        return true;
    };
    int count = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        for (int j = i; j < (int)s.size(); j++) {
            if (isPal(i, j)) count++;
        }
    }
    return count;
}

Flaws & bottlenecks

  • n² substrings each tested in O(n): cubic.
  • The inner comparisons are repeated for every enclosing substring.
  • No early pruning, even though a mismatch at the ends rules out the outside substrings only for the same centre.

Interviewer cross-questions

What work is repeated?

Say: Testing s[i..j] compares s[i] with s[j] and then re-tests s[i+1..j−1]. That inner substring is tested again as its own candidate.

How many substrings are there?

Say: n(n + 1)/2, one for each pair i ≤ j.

How do you cut the cost?

Say: Reuse the inner answer (DP table) or grow palindromes from their centres.

2 · intermediate

DP table

time O(n²)space O(n²)

dp[i][j] is true when s[i] equals s[j] and the substring between them is a palindrome (or has at most two letters). Fill by increasing length and count the true cells.

int countSubstrings(string s) {
    int n = s.size();
    vector<vector<bool>> dp(n, vector<bool>(n, false));
    int count = 0;
    for (int len = 1; len <= n; len++) {
        for (int i = 0; i + len <= n; i++) {
            int j = i + len - 1;
            if (s[i] == s[j] && (len <= 2 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                count++;
            }
        }
    }
    return count;
}

Flaws & bottlenecks

  • O(n²) memory.
  • Computes cells for all substrings even though most are not palindromes.
  • Filling order matters: row by row would read an unfinished inner cell.

Interviewer cross-questions

Why does the length order work?

Say: dp[i][j] depends on dp[i+1][j−1], which is strictly shorter, so all shorter substrings are decided first.

Can the table be avoided?

Say: Yes: expanding from each centre gives the same count with O(1) memory.

What are the base cases?

Say: Length 1 is always a palindrome; length 2 is one exactly when the two letters are equal. The "len <= 2" shortcut encodes both.

3 · advanced

Expand around each centre

time O(n²)space O(1)

For each of the 2n − 1 centres expand outwards while the outer letters match; every successful step is one more palindromic substring.

int countSubstrings(string s) {
    int count = 0;
    auto expand = [&](int l, int r) {
        while (l >= 0 && r < (int)s.size() && s[l] == s[r]) {
            count++;
            l--;
            r++;
        }
    };
    for (int c = 0; c < (int)s.size(); c++) {
        expand(c, c);
        expand(c, c + 1);
    }
    return count;
}

Flaws & bottlenecks

  • A string of identical letters makes every expansion go to the edges: quadratic.
  • It is easy to forget the even-length centres.
  • The count can reach n(n + 1)/2, so for very long strings use a 64-bit integer.

Interviewer cross-questions

Why does each expansion step count one palindrome?

Say: The window [l, r] centred at the same point is a new, larger palindrome each time it grows by one letter on each side, so each successful step adds exactly one substring.

What is the largest possible answer?

Say: n(n + 1)/2, for a string of equal letters. For n = 1000 that is 500,500, which fits easily in 32 bits, but longer inputs would need 64-bit counters.

Can you do it in linear time?

Say: Yes, with Manacher's algorithm, which gets all radii in O(n) and sums (radius + 1) / 2 per centre.

4 · expert

Manacher's algorithm

time O(n)space O(n)

Transform the string with separators, compute the radius p[i] of the longest palindrome at every position using the mirror trick, and add (p[i] + 1) / 2 for each position. Total O(n).

int countSubstrings(string s) {
    string t = "^#"; for (char ch : s) { t += ch; t += '#'; } t += '$';
    vector<int> p(t.size(), 0);
    int center = 0, right = 0, count = 0;
    for (int i = 1; i < (int)t.size() - 1; i++) {
        if (i < right) p[i] = min(right - i, p[2 * center - i]);
        while (t[i + 1 + p[i]] == t[i - 1 - p[i]]) p[i]++;
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
        count += (p[i] + 1) >> 1;
    }
    return count;
}

Flaws & bottlenecks

  • Subtle to implement and to explain; the mirror logic is easy to get wrong.
  • Needs a transformed copy and a radius array.
  • For short strings the simpler expansion is just as fast in practice.

Interviewer cross-questions

Why is (p[i] + 1) / 2 the count?

Say: The palindromes centred at i have lengths p[i], p[i] − 2, p[i] − 4, … down to 1 or 2. That is ceil(p[i] / 2) values, which equals (p[i] + 1) >> 1.

Why is it linear?

Say: The right edge of the right-most palindrome never moves left, and each successful comparison pushes it right, so the total comparisons are bounded by the length of the transformed string.

What changes if you only need yes/no for a given substring?

Say: With the radius array, s[i..j] is a palindrome iff p at the centre position covers it: an O(1) query after O(n) preparation.

Synchronized code walkthrough

Showing: Test every substring — shares the player above; click any step to jump.

int countSubstrings(string s) {
    auto isPal = [&](int l, int r) -> bool {
        while (l < r) {
            if (s[l] != s[r]) return false;
            l++;
            r--;
        }
        return true;
    };
    int count = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        for (int j = i; j < (int)s.size(); j++) {
            if (isPal(i, j)) count++;
        }
    }
    return count;
}