Palindromic Substrings
Problem
Return the number of palindromic substrings. Substrings at different positions count separately, even when their text is the same.
Example 1
Input: "abc" Output: 3
Example 2
Input: "aaa" Output: 6
a, a, a, aa, aa, aaa.
Test cases
Case 1
Input: "abc" Expected: 3
Case 2
Input: "aaa" Expected: 6
Case 3
Input: "a" Expected: 1
View solutionHide solution1 approach
1. Expand around every centre
Time O(n²)Space O(1)
There are 2n − 1 centres (each char and each gap). Expand while the ends match, counting each step.
function countSubstrings(s) { let count = 0; const expand = (l, r) => { while (l >= 0 && r < s.length && s[l] === s[r]) { count++; l--; r++; } }; for (let i = 0; i < s.length; i++) { expand(i, i); expand(i, i + 1); } return count;}The DP table (dp[i][j] = s[i] === s[j] && dp[i+1][j−1]) is also O(n²) but uses O(n²) space.