Palindromic Substrings

Medium Dynamic Programming Strings Original on LeetCode

Palindromic Substrings is a medium dynamic programming problem solved with the strings pattern. The best approach, optimal (expand around center), runs in O(n²) time and O(1) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force up.

Problem

Given a string s, count how many of its substrings are palindromes. A substring is a contiguous, non-empty run of characters, and a palindrome reads the same from left to right as from right to left.

Substrings are counted by position, not by content: two equal substrings that start or end at different indices are counted separately.

Examples

Example 1

Input
s = "aba"
Output
4
Why
The palindromes are "a", "b", "a" and "aba".

Example 2

Input
s = "zzz"
Output
6
Why
Three "z", two "zz" (at different positions) and one "zzz".

Example 3

Input
s = "abc"
Output
3
Why
Only the single letters read the same both ways.

Constraints

  • 1 <= s.length <= 1000
  • s contains only lowercase English letters.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute forceO(n³)O(1)
Better (interval DP table)O(n²)O(n²)
Optimal (expand around center)O(n²)O(1)

1Brute force

TimeO(n³)There are about n²/2 substrings and each check can take O(n).
SpaceO(1)Only a few indices; no substring is copied.

Generate every substring by its start and end index and check each one with two pointers moving inward.

  1. For every start i and every end j >= i, check whether s[i..j] is a palindrome.
  2. The check walks l = i and r = j toward each other and fails on the first mismatch.
  3. Count the substrings that pass.
class Solution {
    public int countSubstrings(String s) {
        int n = s.length(), count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (isPal(s, i, j)) count++;
            }
        }
        return count;
    }

    private boolean isPal(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) return false;
            l++;
            r--;
        }
        return true;
    }
}

2Better (interval DP table)

TimeO(n²)Each of the n²/2 cells is filled in O(1).
SpaceO(n²)The boolean table has n × n cells.

Let pal[i][j] say whether s[i..j] is a palindrome. It is true when the end letters match and the inside s[i+1..j-1] is a palindrome (or has length 0 or 1). Fill the table from short substrings to long ones and count the true cells.

  1. Loop i from n - 1 down to 0 and j from i up to n - 1, so pal[i+1][j-1] is ready before pal[i][j].
  2. pal[i][j] = s[i] == s[j] && (j - i < 2 || pal[i+1][j-1]).
  3. Add 1 to the count for every true cell.
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;
    }
}

3Optimal (expand around center)

TimeO(n²)2n - 1 centers, and each expansion moves at most n/2 steps.
SpaceO(1)Only two pointers and a counter.

Every palindrome has a center: a letter (odd length) or a gap between two letters (even length). From each of the 2n - 1 centers, expand outward while the two ends match; each successful step is one more palindrome.

  1. For each index c, expand from (c, c) for odd lengths and from (c, c + 1) for even lengths.
  2. While l >= 0, r < n and s[l] == s[r]: count one palindrome, then l--, r++.
  3. Return the total.
class Solution {
    public int countSubstrings(String s) {
        int count = 0;
        for (int c = 0; c < s.length(); c++) {
            count += expand(s, c, c);
            count += expand(s, c, c + 1);
        }
        return count;
    }

    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;
    }
}

Edge cases to test

  • A single character: the answer is 1
  • All letters equal: every substring is a palindrome, n(n + 1) / 2 in total
  • Even-length palindromes such as "abba", which have no single middle letter
  • No repeated letters: only the n single letters count

Hints

Hint 1

Every single letter is a palindrome, so the answer is at least n.

Hint 2

A palindrome stays a palindrome when you strip one letter from each end. Turn that around: grow outward from a middle.

Hint 3

There are 2n - 1 possible middles: n letters (odd lengths) and n - 1 gaps between letters (even lengths).

FAQ

What is the best time complexity for Palindromic Substrings?

Optimal (expand around center) runs in O(n²) time and O(1) extra space. 2n - 1 centers, and each expansion moves at most n/2 steps.

Which pattern does Palindromic Substrings use?

It is a dynamic programming problem that uses the strings pattern. Other problems with the same pattern: Edit Distance, Longest Common Subsequence, Longest Palindromic Subsequence.

Is there a brute force solution for Palindromic Substrings?

Yes. Brute force takes O(n³) time and O(1) space. Generate every substring by its start and end index and check each one with two pointers moving inward.

Which edge cases should I test for Palindromic Substrings?

A single character: the answer is 1; All letters equal: every substring is a palindrome, n(n + 1) / 2 in total; Even-length palindromes such as "abba", which have no single middle letter; No repeated letters: only the n single letters count.