Given a string s, count how many of its substrings are palindromes. A substring is a contiguous block of characters, and substrings at different positions are counted separately even if they contain the same letters.
- 1 <= s.length <= 1000
- `s` contains only lowercase English letters
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force generates all O(n^2) substrings and checks each in O(n), so O(n^3). Instead, notice that a palindrome is fully described by its center. If s[l..r] is a palindrome and s[l-1] == s[r+1], then s[l-1..r+1] is one too. So from each of the 2n - 1 centers we expand outwards and every successful expansion is exactly one new palindrome. That is O(n^2) time with no extra memory.
Algorithm
- Loop over every center
cfrom0to2n - 2. - Set
l = c / 2andr = l + c % 2(odd centers sit on a character, even centers between two characters). - While
l >= 0,r < nands[l] == s[r]: add 1 to the count, then movelleft andrright. - Return the count.
O(n^2)Space: O(1)class Solution: def countSubstrings(self, s: str) -> int: n = len(s) count = 0 # 2n - 1 centers: even c sits on a character, odd c sits between two for c in range(2 * n - 1): l, r = c // 2, c // 2 + c % 2 while l >= 0 and r < n and s[l] == s[r]: count += 1 # s[l..r] is a palindrome l -= 1 r += 1 return count