Given a string, s, return the number of palindromic substrings contained in it. A substring is a contiguous sequence of characters in a string. A palindrome is a phrase, word, or sequence that reads the same forward and backward.

palindromic-substrings.js

function countPalindromicSubstrings(s) {
  // d[i][j] answers the question: is substring [i, j) a palindrome?
  const dp = Array(s.length + 1)
    .fill()
    .map(() => Array(s.length + 1).fill(false));
  // so if the word is lever
  // dp[0][5] is the answer (which means size dp size is s.length + 1 x s.length + 1)

  // since every single char is a palindrome, prefill solutions to those subproblems
  // in word "cat", "a" is substring [1, 2)
  for (let i = 0; i < s.length; ++i) {
    dp[i][i + 1] = true;
  }

  // store result
  let count = 0;

  // outer loop iterates substring lenghts
  // so first we check all substrings of length 2 if they are palindromes
  // (any string is a palindrome if first and last char are equal, and whats in between is a palindrome too)
  // (to check the in-between part we can re-use previous solutions)
  // so if we are checking a substring of length 4 = "noon", we check that "n" === "n",
  // and we check if "oo" is a palindrome (we already checked it at the step when we were checking substrings of length 2)
  for (let len = 2; len <= s.length; ++len) {
    // i,j are substring boundaries (kind of like a sliding window)
    // we move it to the right by 1 at every step of the loop
    for (let i = 0, j = len; j <= s.length; ++i, ++j) {
      // i points to the first character of the substring,
      // j points to the next after last character of the substring (not including)
      if (s[i] === s[j - 1] && (len === 2 || dp[i + 1][j - 1])) {
        dp[i][j] = true;
        count += 1;
      }
    }
  }

  // since every single character is a palindrome, add string length to the result
  return count + s.length;
}

export { countPalindromicSubstrings };

// tc: O(n^2) where n is the string length
// sc: O(n^2)