Marauder Bot

Problem

Given a string, count how many of its contiguous substrings are palindromes. Substrings are counted by position, so two substrings with identical characters but different starting points both count separately.

Example. For "aaa", there are 6 palindromic substrings: the three single letters "a", "a", "a", the two pairs "aa", "aa", and the full string "aaa".

Key idea

Testing every substring directly and verifying each one from scratch costs O(n) per substring across O(n²) substrings, which is cubic overall. As with Longest Palindromic Substring, the shortcut is that a substring is a palindrome exactly when its outer two characters match and the substring left after removing them is also a palindrome. So once shorter spans are known, longer spans can be checked in constant time each.

Fill a table by increasing substring length, marking each span as a palindrome using that recurrence, and add one to a running total every time a span comes out true. The equivalent center-expansion view is just as direct for counting: for each of the 2n - 1 possible centers (each character, and each gap between two characters), expand outward one step at a time, and count every successful expansion as one more palindrome, since a successful match at a given radius always corresponds to exactly one distinct palindromic substring.

Solution

function countSubstrings(s: string): number {
  let count = 0;

  for (let center = 0; center < s.length; center++) {
    count += expandAndCount(s, center, center); // odd-length palindromes centered here
    count += expandAndCount(s, center, center + 1); // even-length palindromes centered in the gap
  }

  return count;
}

function expandAndCount(s: string, left: number, right: number): number {
  let matches = 0;

  while (left >= 0 && right < s.length && s[left] === s[right]) {
    matches++; // each successful expansion is one more distinct palindrome
    left--;
    right++;
  }

  return matches;
}

Complexity

Time: O(n²). Every span (or every center-radius combination) is checked exactly once.
Space: O(n²) for the table version; O(1) for the center-expansion version, which only needs a running count.

Watch out for

Every single character is its own palindrome and must be counted, even though it looks trivial.
Even-length palindromes need centers placed between two characters, not just on individual characters.
This is a counting problem, not a search for one answer, so every true table cell (or every successful expansion) contributes to the total rather than only the largest one.

Pattern

Same interval / expand-around-center DP as Longest Palindromic Substring, with the output changed from "track the longest span found" to "tally every span that qualifies."

Palindromic Substrings