Palindromic Substrings

The problem

Given a string text, return how many of its substrings are palindromes, reading the same forwards and backwards. A substring is a run of letters next to each other. Substrings at different positions count separately, even if they hold the same letters.

Example 1

Input: text = "abaa"

Output: 6

The four single letters, plus “aba” and “aa”.

text

a0b1a2a3

Example 2

Input: text = "xyz"

Output: 3

Only the single letters.

Example 3

Input: text = "zzz"

Output: 6

“z” three times, “zz” twice (at positions 0 and 1), and “zzz” once.

Constraints

• 1 ≤ text.length ≤ 1000 (call it n)
• Only lowercase English letters.

Clarifying questions

Does a single letter count?

Yes. Every letter is a palindrome of length 1.

Do equal substrings at different places count twice?

Yes. In "zzz", "zz" counts twice.

Substring or subsequence?

Substring: the letters must be next to each other.

Spot the pattern

This is the counting version of Longest Palindromic Substring. A palindrome grows from its middle by adding one matching letter on each side. So two pointers moving outward from a middle meet every palindrome with that middle, one per step, and stop at the first mismatch.

Solutions

Expand around centersO(n²)

Show all

There is only one approach worth showing here. Checking every substring on its own works, but costs O(n³), exactly as in Longest Palindromic Substring, and a table of palindromes costs O(n²) memory for the same time.

Expand around centers O(n²)

The idea

Every palindrome has exactly one middle: a letter if its length is odd, the gap between two letters if its length is even. So go through all 2n − 1 middles.

From a middle, put left and right on its two sides. While they are inside the string and text[left] == text[right], the letters from left to right form a palindrome: count it, and move both pointers one step out. The first mismatch ends this middle, because any longer string with the same middle has that mismatch inside it.

Why it counts each palindrome once: each palindrome is found from its own middle, at the step where the pointers reach its two ends, and from no other middle.

Walkthrough

text

a0b1a2a3

count

0

found

-

1. count = 0
2. for center in 0 .. len(text) - 1:
3. for (left, right) in (center, center), (center, center + 1): # letter or gap
4. while left >= 0 and right < len(text) and text[left] == text[right]:
5. count += 1; left -= 1; right += 1
6. return count

Every palindrome has a middle: a letter for odd lengths, a gap for even lengths. From each middle, step outward. Each step where the two ends still match is one more palindrome.

← BackStep →Play1 / 9

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Expand around each center: every palindrome has a middle letter or gap.
    // Each step outward that still matches is one more palindrome. O(n²) time, O(1) space.
    public int countSubstrings(String text) {
        int count = 0;
        for (int center = 0; center < text.length(); center++) {
            // Odd lengths have a middle letter; even lengths have a middle gap.
            count += expand(text, center, center) + expand(text, center, center + 1);
        }
        return count;
    }

    private int expand(String text, int left, int right) {
        int found = 0;
        while (left >= 0 && right < text.length() && text.charAt(left) == text.charAt(right)) {
            // text[left..right] reads the same both ways.
            found++;
            left--;
            right++;
        }
        return found;
    }
}

Big O

Time O(n²)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The outer loop tries 2 middles per letter. For each, the while loop compares one pair of letters per run. Both are fixed jobs, so each middle and each pair compared counts as 1 step.

   1. count = 0
   2. for center in 0 .. len(text) - 1:
   3. for (left, right) in (center, center), (center, center + 1): # letter or gap
   4. while left >= 0 and right < len(text) and text[left] == text[right]:
   5. count += 1; left -= 1; right += 1
   6. return count

2. 2 Count the runs on Example 1

   The table has one column per letter, with its letter middle and its gap middle. Each number is how many pairs that middle compared, including the one that failed.

   8 middles + 9 pairs = 17 steps.

   c	0	1	2	3
   letter middle	1	2	2	1
   gap middle	1	1	1	0

   total

   8 middles + 9 pairs = 17 steps

3. 3 Write the count for any n

   There are 2 × n middles in the loop, and from each, the pointers move at most n / 2 places before one falls off an end. So each compares at most n / 2 + 1 pairs:

   2 × n × (1 + n / 2 + 1) = n² + 4 × n steps

   Check it with Example 1: 16 + 16 = 32 at most. The real run used 17. A string of one letter repeated reaches the bound, and it really has about n² / 2 palindromes to count.

4. 4 Keep only the part that grows fastest

   Drop the 4 × n. What is left is n². No method that counts the palindromes one at a time can beat this, since there can be about n² / 2 of them.

   So the time is O(n²).

5. S Space: count the extra memory the same way

   Just the count and two pointers. So the space is O(1).

   countleft, right

Common mistake

Expanding past a mismatch

Once text[left] != text[right], stop. It can be tempting to keep going to look for more matches further out, but every longer substring with this middle contains the mismatched pair, so none of them is a palindrome.

Tested at the limits

2,000 random strings of 1 to 14 letters, made of one, two or three different letters. Expand around centers gave the same count every time as a simple check that reverses every substring.

Largest inputs	Result
1,000 copies of one letter (the most allowed), so all 500,500 substrings are palindromes. Expand around centers.	0.05 s, and under 0.001 MB of extra memory: just the count and two indexes.