Problem 31.6 · DP on Strings and SequencesMedium

Palindromic Substrings

What it teaches: Counting palindromes: expand from 2n − 1 centres, or a boolean interval table.

Practise it on judges as “Palindromic Substrings”.

The problem

Return the number of palindromic substrings (counted by position) in s.

Example 1

Input: s = "aaa"
Output: 6

Constraints

1 ≤ n ≤ 1000

Pattern clues in the wording

→ Count contiguous palindromes

These clues point to Expand Around Center: Treat every index (and every gap between two indexes) as the middle of a palindrome and grow outwards while both sides match.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int countSubstrings(String s) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	s = "abc"	3
2	s = "aaa"	6

From slow to fast

Approaches

1. Expand around centres · O(n²)2. Boolean interval DP · O(n²)

Expand around centres

Time O(n²) Space O(1)

For each of the 2n − 1 centres, expand while the ends match, counting each step.

Approach 1

class Solution {
    public int countSubstrings(String s) {
        int count = 0;
        for (int c = 0; c < 2 * s.length() - 1; c++) {
            int l = c / 2, r = l + c % 2;
            while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { count++; l--; r++; }
        }
        return count;
    }
}

Verdict: Simplest.

Boolean interval DP

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

pal[i][j] = s[i] == s[j] && (j − i < 2 || pal[i + 1][j − 1]).

Approach 2

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

Verdict: Gives a reusable table (useful for palindrome partitioning).

Before you submit

Edge cases and common mistakes

Test these inputs

Single character
All equal characters (n(n + 1) / 2)

Mistakes people make

Only expanding odd-length centres.

Interview

Follow-up questions

Can it be done in O(n)?

Command Palette