Overview

Given a string s, return the number of palindromic substrings in it.

A substring is a contiguous sequence of characters within the string. A string is palindromic if it reads the same backward as forward.

Constraints

• 1 <= s.length <= 1000
• s consists of lowercase English letters.

Examples

countSubstrings("abc");
// => 3  ("a", "b", "c")

countSubstrings("aaa");
// => 6  ("a", "a", "a", "aa", "aa", "aaa")

Solution

function countSubstrings(s) {
  let count = 0;

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

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

  return count;
}

Resources

• Palindromic Substrings — LeetCode
• Palindrome — Wikipedia