Palindromic Substrings

The problem

A palindrome reads the same forward and backward. Return how many substrings of s are palindromes. A substring is a run of characters that sit next to each other in s, and a single character counts. Substrings at different positions are counted separately, even when they hold the same letters.

What to write

function solve(s: string): number

Input
s = "abc"

Output
3

Input
s = "aaa"

Output
6

Constraints

1 ≤ s.length ≤ 1000.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   s has at most 1000 characters, so it has up to 500,500 substrings. When all the letters are equal, every one of them is a palindrome, so the answer itself can be that large. What you can save is the work spent on each substring.

2. Hint 2: Ask a smaller question

   Take "abba". Which of its palindromes have their middle between the two b letters? Write them from shortest to longest. What had to be true of the letters you added to get from one to the next?

3. Hint 3: Name the pattern

   Every palindrome has one middle: a single letter, or two letters side by side. Start at each middle and grow outward one letter on each side while the two ends match. Every round that succeeds is one more palindrome. This is called expand around a center. Read the lesson on expand around a center.

4. Hint 4: State the invariant

   Each palindrome is counted exactly once, from its own center. While the two ends match, the piece between them is a palindrome. As soon as they differ or an end leaves s, no wider piece around that center can be one.

5. Hint 5: Sketch the pseudocode

   count = 0. For each position i and offset 0, then 1: left = i, right = i + offset. While both are inside s and their letters match: add 1 to count, then step left down and right up. Return count.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Every palindrome has one odd or even center. Count each successful outward expansion.

The slow way

Check every substring: read it from both ends inward and count the ones that are palindromes. It is correct, but there are about n × n / 2 substrings, and one check can take about n / 2 comparisons. For 1000 equal letters that comes to 83,458,250 comparisons.

The insight

Every palindrome has exactly one center: its middle letter, or its two middle letters. Growing outward from a center one letter on each side meets the palindromes around that center one after another, each for the price of a single comparison. So count one for every round that succeeds, over all centers.

Step by step

1. Start the count at 0. Nothing has been found yet. Every palindrome that turns up below adds 1 to this count.
2. Try each center in turn: one letter, then that letter and the next. A palindrome of odd length, such as "aba", has one middle letter. A palindrome of even length, such as "abba", has two. Trying both kinds at every position reaches every palindrome in s.
3. While both ends are inside s and hold the same letter. Matching ends around a palindrome make a longer palindrome. A mismatch, or an end outside s, means no wider piece around this center can be a palindrome, so the loop stops here.
4. The piece from end to end is a palindrome: count it. Each round of the loop is a different piece of s, with its own start and end. So adding 1 per round counts every palindrome once, including equal texts at different positions.
5. Move both ends one letter outward. The next candidate around the same center is one letter wider on each side. Only its two new end letters need comparing, because the letters between them already matched.
6. Return the count. Every center has been tried, and every palindrome belongs to exactly one center, so nothing was missed and nothing was counted twice.

The same numbered steps are the comments in each solution.

function solve(s) {
  // 1. Start the count at 0
  let count = 0;
  // 2. Try each center in turn: one letter, then that letter and the next
  for (let i = 0; i < s.length; i++)
    for (const offset of [0, 1]) {
      let left = i;
      let right = i + offset;
      // 3. While both ends are inside s and hold the same letter
      while (left >= 0 && right < s.length && s[left] === s[right]) {
        // 4. The piece from end to end is a palindrome: count it
        count++;
        // 5. Move both ends one letter outward
        left--;
        right++;
      }
    }
  // 6. Return the count
  return count;
}

function solve(s: string): number {
  // 1. Start the count at 0
  let count = 0;
  // 2. Try each center in turn: one letter, then that letter and the next
  for (let i = 0; i < s.length; i++)
    for (const offset of [0, 1]) {
      let left = i;
      let right = i + offset;
      // 3. While both ends are inside s and hold the same letter
      while (left >= 0 && right < s.length && s[left] === s[right]) {
        // 4. The piece from end to end is a palindrome: count it
        count++;
        // 5. Move both ends one letter outward
        left--;
        right++;
      }
    }
  // 6. Return the count
  return count;
}

def solve(s):
    # 1. Start the count at 0
    count = 0
    # 2. Try each center in turn: one letter, then that letter and the next
    for i in range(len(s)):
        for offset in (0, 1):
            left = i
            right = i + offset
            # 3. While both ends are inside s and hold the same letter
            while left >= 0 and right < len(s) and s[left] == s[right]:
                # 4. The piece from end to end is a palindrome: count it
                count += 1
                # 5. Move both ends one letter outward
                left -= 1
                right += 1
    # 6. Return the count
    return count

Example 2, traced

Input
s = "aaa"

Output
6

Why it works

A palindrome is found from its own center and from no other, because its middle sits in one place. From that center the loop passes through every palindrome around the center, shortest first, and stops only when no wider one can exist. So each palindrome in s adds exactly 1 to the count.

Time and space

Time O(n²), extra space O(1). There are 2n centers for n letters. From one center the ends can move outward at most about n / 2 times before one of them leaves s, so the time is O(n²). Only the count and two positions are kept, so the extra space is O(1).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Try the two-letter centers as well. With one-letter centers only, every palindrome of even length is missed, and example 2 gives 4 instead of 6.
• Count positions, not texts. If you store the palindromes in a set, which keeps one copy of equal texts, example 2 gives 3 instead of 6.
• In Python, check that the left end is at least 0 before you read its letter. Position -1 means the last letter, so without the check the loop counts pieces that do not exist: "cc" gives 4 instead of 3.

Pattern

Expand around a center. Builds on Longest Palindromic Substring.

Keep going