The problem. Given a string s, return how many of its substrings are palindromes. Substrings at different positions count separately, even if they contain the same letters.
s = "abc" -> 3 ("a", "b", "c")
s = "aaa" -> 6 ("a", "a", "a", "aa", "aa", "aaa")
s = "abba" -> 6 ("a", "b", "b", "a", "bb", "abba")A palindrome is a mirror image around its middle. If you know s[i..j] is a palindrome, then s[i-1..j+1] is one exactly when the two new end letters are equal. So instead of testing each substring separately, start from a middle and grow outwards one step at a time, counting every step that still matches — and stop at the first mismatch, because nothing wider with that middle can be a palindrome.
Odd-length palindromes have a letter in the middle ("aba"), even-length ones have a gap ("abba"). A string of n letters has n letters and n - 1 gaps: 2n - 1 middles. Growing from all of them finds every palindromic substring, in O(n²) time and O(1) space.
function countSubstrings(s) { const isPal = (i, j) => { while (i < j) if (s[i++] !== s[j--]) return false; return true; }; let count = 0; for (let i = 0; i < s.length; i++) { for (let j = i; j < s.length; j++) { if (isPal(i, j)) count++; // check s[i..j] from scratch } } return count;}Time O(n³), space O(1). About n² / 2 substrings, each checked in up to O(n). Checking "abba" repeats the work of checking "bb".
From each of the 2n - 1 middles, every step outwards that still matches is one more palindrome.
function countSubstrings(s) { let count = 0; const expand = (left, right) => { // grow outwards while the ends match while (left >= 0 && right < s.length && s[left] === s[right]) { count++; // s[left..right] is a palindrome left--; right++; } }; for (let center = 0; center < s.length; center++) { expand(center, center); // odd length: one middle letter expand(center, center + 1); // even length: the gap after it } return count;}Time O(n²), space O(1). 2n - 1 middles, and each grows at most n / 2 steps. A string of identical letters is the worst case: every step matches.
A dynamic-programming table (pal[i][j] is true when the ends match and pal[i+1][j-1] is true) also counts them in O(n²) time, but needs O(n²) memory. Expanding gets the same speed for free. Manacher's algorithm does it in O(n), but it's rarely expected in interviews.
"aaaa" has 10."aa" would give 2 instead of 3.