Palindromic Substrings

Examples

Input: s = "abc"
Output: 3

"a", "b", and "c" are each a palindrome on their own; no longer substring is.

Input: s = "aaa"
Output: 6

Three single "a"s, two "aa"s (positions 0-1 and 1-2), and one "aaa".

Constraints

• 1 <= s.length <= 1000

• s consists of lowercase English letters

Approach

Just like the longest-palindrome version of this problem, every palindromic substring is defined by its center and how far it stretches outward from that center. If you check all 2n - 1 possible centers (one for each character, plus one for each gap between adjacent characters) and, for each one, expand outward for as long as both sides keep matching, then every single step of that expansion corresponds to exactly one distinct palindromic substring.

So rather than tracking the longest one, simply add 1 to a running count every time the expansion successfully matches — that count, once every center has been tried, is the total number of palindromic substrings.

Solutions

Brute Force — Check Every Substring

Generate every substring and test each one for being a palindrome, counting up the ones that pass.

function countSubstrings(s) {
  function isPalindrome(str) {
    let left = 0;
    let right = str.length - 1;
    while (left < right) {
      if (str[left] !== str[right]) return false;
      left++;
      right--;
    }
    return true;
  }

  let count = 0;
  for (let i = 0; i < s.length; i++) {
    for (let j = i; j < s.length; j++) {
      if (isPalindrome(s.slice(i, j + 1))) count++;
    }
  }
  return count;
}

Time: O(n^3) — O(n^2) substrings, each checked in O(n) · Space: O(1) extra, ignoring the substrings themselves

Optimal — Expand Around Center

Try every possible center (each character, and each gap between two characters) and expand outward while both sides mirror, counting one palindrome for every successful step of the expansion.

function countSubstrings(s) {
  let count = 0;

  function expand(left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      count++;
      left--;
      right++;
    }
  }

  for (let i = 0; i < s.length; i++) {
    expand(i, i);       // odd-length palindromes centered on i
    expand(i, i + 1);   // even-length palindromes centered between i and i+1
  }

  return count;
}

Time: O(n^2) · Space: O(1) extra