Palindromic Substrings
Medium1-D dynamic programming
Given a string s, return how many of its substrings read the same forwards and backwards. A substring is a run of characters next to each other in s.
Substrings at different positions count separately, even when they hold the same letters. Every single character is a palindrome.
Examples
Input: s = "aba" Output: 4
a, b, a and aba.
Input: s = "bbbc" Output: 7
Four single letters, two bb’s at different positions, and bbb.
Constraints
1 ≤ s.length ≤ 1000sholds lowercase English letters only.
Stuck?
Hint 1
Every palindrome has a centre: one character, or the gap between two. Each step outwards that still matches is one more palindrome.
Hint 2
Try all 2n - 1 centres. From each, expand while the two ends match, adding one to the count at every step.
The idea
Every palindrome has exactly one centre, a character or the gap between two, and it can be reached by growing out from that centre. Each step outwards that still matches is one more palindrome. So counting the matching steps from all 2n - 1 centres counts every palindromic substring exactly once.
Time O(n²)Extra space O(1)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 4
One loop numbers all the centres. An even centre is a character, so left and right both start on it. An odd one is the gap after a character, so right starts one place to the right of left.
function countSubstrings(s) { let count = 0; for (let centre = 0; centre < 2 * s.length - 1; centre++) { let left = Math.floor(centre / 2); let right = left + (centre % 2); while (left >= 0 && right < s.length && s[left] === s[right]) { count++; left--; right++; } } return count;}The trap
Starting every window on a single character counts each odd-length palindrome, so the answer looks right on strings with no two equal letters side by side. An even-length palindrome is centred on a gap, and a window that starts on one character never covers it. Any string with two equal neighbours gets too low a count.
function countSubstrings(s) { let count = 0; for (let i = 0; i < s.length; i++) { let left = i; let right = i; while (left >= 0 && right < s.length && s[left] === s[right]) { count++; left--; right++; } } return count; // misses the even-length ones}