Palindromic Substrings

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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.