Palindromic Substrings

Problem

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

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

Example 1:

Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Constraints:

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

Solution

/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function(s) {
    let count = 0;
    for (let i = 0; i < s.length; i++) {
        count += expandAroundCentre(s, i, i); // odd length
        count += expandAroundCentre(s, i, i + 1); // even length
    }
    return count;
};

var expandAroundCentre = function(s, left, right) {
    let count = 0;
    while (left >= 0 && right < s.length && s[left] === s[right]) {
        count++;
        left -= 1;
        right += 1;
    }
    return count;
};

We find the number of palindrome substrings by trying every possible palindrome centre and expanding around it (ie. given a palindrome, if the characters directly before and after it are the same, we must have another palindrome). There are 2n - 1 of such centres that needs to be tested, while keeping track of the number of palindrome substrings already encountered.

Problem​

Solution​

Problem

Solution