Count Palindromic Substrings
You get a string s made of lowercase English letters.
A substring is a block of characters that sit next to each other in s. It is fixed by its start index and its end index.
A palindrome reads the same from left to right and from right to left.
Return how many substrings of s are palindromes.
Counting rules
- Every single character is a palindrome, so it counts. A string of length
nalways has at leastn. - Substrings at different positions are counted separately, even when their text is the same.
Hint
Every palindrome has a centre. The centre is either one character (odd length) or the gap between two characters (even length). From each of the 2n - 1 centres, grow outwards while the two ends match, and count each step.
Examples
Example 1
- Input:
- "pqr"
- Output:
- 3
Only the three single letters "p", "q" and "r" are palindromes.
Example 2
- Input:
- "bbb"
- Output:
- 6
Three single letters, two copies of "bb" (at index 0 and at index 1), and "bbb": 3 + 2 + 1 = 6.
Example 3
- Input:
- "level"
- Output:
- 7
Five single letters, plus "eve" and "level": 5 + 2 = 7.
Constraints
1 <= s.length <= 60shas only lowercase English letters.
Run checks your code against the 3 examples. Submit checks it against all 263 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.