Q44: Palindromic Substrings (Expand Around Center)
Given a string s, return the count of palindromic substrings in s using Expand Around Center method.
Center Expansion Palindrome Counter
function countSubstrings(s) {
let count = 0;
function expand(left, right) {
let found = 0;
while (left >= 0 && right < s.length && s[left] === s[right]) {
found++;
left--;
right++;
}
return found;
}
for (let i = 0; i < s.length; i++) {
count += expand(i, i); // Odd length center
count += expand(i, i + 1); // Even length center
}
return count;
}
console.log(countSubstrings('aaa')); // 6 ('a','a','a','aa','aa','aaa')💡 Iterates every character index, expanding outward for odd-length palindromes (
i, i) and even-length palindromes (i, i+1), incrementing counts while characters match.Key Takeaways
- Consider $2n - 1$ possible expansion centers (odd single characters and even adjacent character pairs).
- Achieves $O(n^2)$ time and $O(1)$ space complexity.
Knowledge Check
How many total potential palindrome centers exist for a string of length N?