A palindrome reads the same from left to right as from right to left, like eye or noon. A substring is a run of consecutive characters.
Given a string s, count its substrings that are palindromes. Substrings are counted by position: two equal substrings that start or end at different places count separately.
The five single letters, plus eve (the middle three) and level (the whole string).
The four single letters, plus aba and bab. The two palindromes overlap, which is fine.
z at position 0, z at position 1, and zz. The two single zs are equal but sit at different positions, so both count.
Constraints
1 <= s.length <= 1000s is made of lowercase English letters only.Every palindrome has a middle: one letter (odd length) or the gap between two letters (even length). A string of length n has 2n − 1 middles.
A palindrome is built from the middle out. Peel the first and last letters off one, and what's left is a shorter palindrome around the same middle. Turn that around: start at a middle and add one letter on each side. As long as the two new letters match, you've made one more palindrome. The first time they don't match, nothing bigger around this middle can be one, because every bigger one would need that pair to match.
Time O(n²)Space O(1)
The full walkthrough and code are part of Premium
7