—
center
Count every palindromic substring by treating each of the 2n − 1 possible centers as a seed and expanding outward with two pointers — each successful expansion is exactly one new palindrome.
Given a string s, return the number of substrings that are palindromes. Every single character counts. For s = "aaa" the palindromic substrings are "a" (×3), "aa" (×2), and "aaa" (×1) — six total, so the answer is 6. For s = "abc" only the three single characters qualify, giving 3.
n odd-length centers (single characters) and n − 1 even-length centers (gaps between characters) — 2n − 1 centers total. Seed each one, expand both pointers outward while s[l] === s[r], and increment count on every match: that expansion is a distinct palindrome.c from 0 to 2n − 2. Odd centers (c even) start at l = r = c / 2. Even centers (c odd) start at l = ⌊c/2⌋, r = l + 1. One loop, no branches needed.while (l >= 0 && r < n && s[l] === s[r]): increment count, then move l--; r++. Each iteration is a confirmed new palindrome.s[l] !== s[r] (or a pointer goes out of bounds), break — no wider palindrome can exist at this center.count holds the total.c = 0..2n-2 trick unifies them: when c is even r starts equal to l (odd-length), when c is odd r = l + 1 (even-length). One loop, no missed cases.The O(n) Manacher's algorithm reuses previously computed palindrome radii to skip redundant expansions. It's rarely asked in interviews — expand-around-center at O(n²) is the expected answer. Mention Manacher's as a follow-up to show depth.
"aaa", length 3. Iterating 5 centers (3 odd + 2 even). Count = 0.function countSubstrings(s: string): number {
let count = 0;
const n = s.length;
// Try every possible center (n odd + n-1 even = 2n-1 centers)
for (let c = 0; c < 2 * n - 1; c++) {
let l = Math.floor(c / 2);
let r = l + (c % 2 === 0 ? 0 : 1); // odd center: r = l; even: r = l+1
// Expand outward while characters match
while (l >= 0 && r < n && s[l] === s[r]) {
count++;
l--;
r++;
}
}
return count;
}count accumulates every palindrome found. nis cached so we don't recompute the length.c = 0..2n-2 encodes both odd and even centers. When c % 2 === 0, both pointers start at the same character (odd-length palindrome seed). When c % 2 === 1, r = l + 1 seeds an even-length palindrome across the gap. No separate loops needed.s[l] === s[r] confirms a distinct palindromic substring — count it, then widen. The while condition l >= 0 && r < n guards bounds before the character comparison.count holds the exact number of palindromic substrings.2n − 1 centers, each expands at most O(n/2) steps. O(1) extra space — only two integer pointers and a counter.s.slice(start - radius, start + radius + 1).isPalin[i][j] table, then backtrack using it as an O(1) check.n*(n+1)/2 — a good sanity check for your solution.| "count palindromic substrings" | expand around center (2n−1 seeds) |
| "longest palindromic substring" | expand around center, track max radius |
| symmetric structure around a midpoint | two-pointer expansion from center |
| "palindrome partition / precompute isPalin" | run expand-center to fill table |
function countSubstrings(s: string): number {
let count = 0;
const n = s.length;
for (let c = 0; c < 2 * n - 1; c++) {
let l = Math.floor(c / 2);
let r = l + (c % 2 === 0 ? 0 : 1);
while (l >= 0 && r < n && s[l] === s[r]) {
count++;
l--;
r++;
}
}
return count;
}2n − 1: n odd-length centers (single chars) + (n−1) even-length centers (gaps between chars).s = "aaa", how many palindromic substrings are there?c is odd, what are the starting values ofl and r?count inside the while loop (before moving the pointers) give the correct total?"aaaa", length n) has how many palindromic substrings?