Palindromic Substrings

Medium · 1-D Dynamic Programming

You are given a string made of lowercase letters. Count how many contiguous substrings of it read the same forwards and backwards. Substrings that occupy different positions count separately even if the characters they contain are identical.

Examples

Input:  s = "abc"
Output: 3
Why:    Only the three single letters a, b, c are palindromes; no longer substring reads the same both ways.

Input:  s = "aaa"
Output: 6
Why:    The palindromic substrings are a, a, a, aa, aa, aaa, giving 6 total.

Input:  s = "racecar"
Output: 10
Why:    The 7 single letters are palindromes, plus cec, aceca, and the full word racecar, totaling 10.

Constraints

1 <= s.length <= 1000, s consists of lowercase English letters

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Palindromic Substrings

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Palindromic Substrings. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.