104.Palindromic Substrings

MediumBlind 751-D Dynamic Programming · 6/12

Problem

Given a string s, return how many of its substrings are palindromes.

A substring is a contiguous, non-empty block of characters. Substrings at different positions count separately even if they contain the same characters (in "aaa", each single "a" counts).

Examples

Input:  s = "abc"
Output: 3
Explanation: "a", "b", "c".

Input:  s = "aaa"
Output: 6
Explanation: "a", "a", "a", "aa", "aa", "aaa".

Input:  s = "abba"
Output: 6
Explanation: "a", "b", "b", "a", "bb", "abba".

Constraints

1 <= s.length <= 1000
s consists of lowercase English letters.

💡 Key Insight

This is Longest Palindromic Substring with "count" instead of "max". s[i..j] is a palindrome iff s[i] == s[j] and s[i+1..j-1] is a palindrome, so a DP over (i, j) counts them in O(n²). Equivalently, every palindrome has a unique centre (one of 2n - 1 characters or gaps), and expanding outward from a centre discovers the palindromes there one per successful step — O(n²) time and O(1) space. Manacher's radii p[i] give each centre's count directly as (p[i] + 1) / 2, for O(n) overall.

Brute Force

TimeO(n³)SpaceO(1).

Intuition

Enumerate all n(n+1)/2 substrings and test each one with two pointers.

Algorithm

count = 0.
For every i and every j >= i, if s[i..j] is a palindrome, count++.
Return count.

Visualization

s = "aaa"
i=0: "a" ✓  "aa" ✓  "aaa" ✓
i=1: "a" ✓  "aa" ✓
i=2: "a" ✓
count = 6

Code

java

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (isPalindrome(s, i, j)) {
                    count++;
                }
            }
        }
        return count;
    }

    private boolean isPalindrome(String s, int lo, int hi) {
        while (lo < hi) {
            if (s.charAt(lo++) != s.charAt(hi--)) {
                return false;
            }
        }
        return true;
    }
}

Complexity

Time: O(n³) — O(n²) substrings, O(n) check each.
Space: O(1).

Top-Down Memoization

TimeO(n²)SpaceO(n²)

Intuition

The palindrome test for s[i..j] repeats the test for s[i+1..j-1], which was already done when that shorter substring was counted. Cache pal(i, j).

Recurrence: pal(i, j) = true if i >= j, else (s[i] == s[j]) && pal(i + 1, j - 1). Answer = number of pairs i <= j with pal(i, j).

Algorithm

Boolean[][] memo (null = unknown).
For every i <= j, call pal(i, j); add 1 if true.
pal returns the cached value or computes it via the recurrence.

Visualization

s = "abba". The outer loop asks about many pairs; the shared inner pairs are computed once.

flowchart TD
    A["pal(0,3) 'abba'"] -->|"a == a"| B["pal(1,2) 'bb'"]
    B -->|"b == b"| C["pal(2,1) = true (empty)"]
    D["outer loop asks pal(1,2)"] -->|"cache hit"| B
    E["pal(0,2) 'abb'"] -->|"a != b"| F["false"]
    G["pal(1,3) 'bba'"] -->|"b != a"| H["false"]

Code

java

class Solution {
    private Boolean[][] memo;
    private String s;

    public int countSubstrings(String s) {
        this.s = s;
        int n = s.length();
        memo = new Boolean[n][n];
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (pal(i, j)) {
                    count++;
                }
            }
        }
        return count;
    }

    private boolean pal(int i, int j) {
        if (i >= j) {
            return true;
        }
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        boolean result = s.charAt(i) == s.charAt(j) && pal(i + 1, j - 1);
        memo[i][j] = result;
        return result;
    }
}

Complexity

Time: O(n²) — each pair computed once.
Space: O(n²) — memo table.

Bottom-Up Tabulation

TimeO(n²).SpaceO(n²).

Intuition

Fill dp[i][j] for i from n - 1 down to 0 and j from i upward, so dp[i + 1][j - 1] is ready. Every true cell is one palindrome.

Recurrence: dp[i][j] = s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1]).

Algorithm

boolean[][] dp = new boolean[n][n], count = 0.
For i = n-1 .. 0, j = i .. n-1: apply the recurrence; if true, count++.
Return count.

Dry Run

s = "aaa":

i \ j	0 a	1 a	2 a
0 a	T	T	T
1 a		T	T
2 a			T

Six T cells → 6. dp[0][2] uses dp[1][1], which was filled on the previous row.

Code

java

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int count = 0;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1]);
                if (dp[i][j]) {
                    count++;
                }
            }
        }
        return count;
    }
}

Complexity

Time: O(n²).
Space: O(n²).

Expand Around Center

TimeO(n²)SpaceO(1).

Intuition

From each of the 2n - 1 centres, grow outward while the ends match. Each successful step is a new palindrome with that centre, so count them as you go; the first mismatch ends that centre, because any larger window around it contains the mismatched pair.

Algorithm

For each i: count += expand(i, i) + expand(i, i + 1).
expand(l, r): while in bounds and s[l] == s[r]: found++, l--, r++. Return found.

Dry Run

flowchart LR
    A["s = 'aaa'"] --> B["centre 0: 'a' → 1"]
    A --> C["gap 0-1: 'aa' → 1"]
    A --> D["centre 1: 'a', 'aaa' → 2"]
    A --> E["gap 1-2: 'aa' → 1"]
    A --> F["centre 2: 'a' → 1"]
    B --> G["total = 6"]
    C --> G
    D --> G
    E --> G
    F --> G

Code

java

class Solution {
    public int countSubstrings(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            count += expand(s, i, i);     // odd-length palindromes
            count += expand(s, i, i + 1); // even-length palindromes
        }
        return count;
    }

    // number of palindromes centred at (l, r)
    private int expand(String s, int l, int r) {
        int found = 0;
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            found++;
            l--;
            r++;
        }
        return found;
    }
}

Complexity

Time: O(n²) — worst case "aaaa...", where every centre expands to the edge.
Space: O(1).

Manacher's AlgorithmOptimal

TimeO(n)SpaceO(n)

Intuition

Transform s into t = ^#s0#s1#...#$ so all palindromes are odd-length, and compute p[i] = palindrome radius at each centre of t using the mirror trick (p[i] >= min(right - i, p[2*center - i])). A centre with radius p[i] contains palindromes of radius p[i], p[i] - 2, ... in t, which correspond to exactly (p[i] + 1) / 2 palindromes in s. Sum those.

Algorithm

Build t with sentinels; p = new int[m], center = right = 0.
For i = 1 .. m-2: seed p[i] from its mirror if i < right, expand while t[i + p[i] + 1] == t[i - p[i] - 1], update center/right if extended.
Return Σ (p[i] + 1) / 2.

Dry Run

s = "aaa" → t = ^ # a # a # a # $:

i	1	2	3	4	5	6	7
t[i]	#	a	#	a	#	a	#
p[i]	0	1	2	3	2	1	0
(p+1)/2	0	1	1	2	1	1	0

Sum = 6. p[4] = 3 means "aaa" and "a" are both centred at the middle a → 2.

Code

java

class Solution {
    public int countSubstrings(String s) {
        StringBuilder sb = new StringBuilder("^");
        for (char c : s.toCharArray()) {
            sb.append('#').append(c);
        }
        sb.append("#$");
        char[] t = sb.toString().toCharArray();
        int m = t.length;
        int[] p = new int[m];
        int center = 0, right = 0;
        int count = 0;

        for (int i = 1; i < m - 1; i++) {
            if (i < right) {
                p[i] = Math.min(right - i, p[2 * center - i]); // mirror shortcut
            }
            while (t[i + p[i] + 1] == t[i - p[i] - 1]) {
                p[i]++;
            }
            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }
            count += (p[i] + 1) / 2; // palindromes in s centred here
        }
        return count;
    }
}

Complexity

Time: O(n) — the right boundary only moves forward.
Space: O(n) — transformed string and radii.

Complexity Comparison

Approach	Time	Space
Brute Force	O(n³)	O(1)
Top-Down Memoization	O(n²)	O(n²)
Bottom-Up Tabulation	O(n²)	O(n²)
Expand Around Center	O(n²)	O(1)
Manacher's Algorithm	O(n)	O(n)

Common Pitfalls

Counting only odd centres — "aa" has 3 palindromes, not 2.
De-duplicating by content (e.g. a HashSet<String>): identical substrings at different positions must each be counted.
Iterating i upward in the DP table, reading dp[i + 1][j - 1] before it is computed.
In Manacher, adding p[i] instead of (p[i] + 1) / 2 — that double-counts via the # positions.