32. Palindromic Substrings
Problem Statement
Given a string s
, return the number of palindromic substrings in it.
A string is a palindrome when it reads the same backward as forward.
A substring is a contiguous sequence of characters within the string.
Example 1:
Input: s = "abc" Output: 3 Explanation: Three palindromic strings: "a", "b", "c".
Example 2:
Input: s = "aaa" Output: 6 Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
Solution
class Solution:
def countSubstrings(self, s: str) -> int:
count = 0
n = len(s)
def expand_around_center(left, right):
nonlocal count
while left >= 0 and right < n and s[left] == s[right]:
count += 1 # Found a new palindromic substring
left -= 1
right += 1
for i in range(n):
# Odd length palindromes (e.g., "aba"), center is s[i]
expand_around_center(i, i)
# Even length palindromes (e.g., "abba"), center is between s[i] and s[i+1]
expand_around_center(i, i + 1)
return count
Explanation
This problem is a variation of the "Longest Palindromic Substring" problem. Instead of finding the longest one, we need to count all of them.
The "expand around center" approach is very suitable here.
-
Iterate through potential centers: Every single character in the string can be the center of an odd-length palindrome (e.g.,
a
inb_a_b
). Every pair of adjacent characters can be the center of an even-length palindrome (e.g.,bb
ina_bb_a
). -
expand_around_center
function:- This helper function takes
left
andright
pointers, representing the initial center(s). - It expands outwards from these pointers as long as the characters match and are within the string boundaries.
- Crucially, every time a match is found and the pointers are expanded, it means we have found a new palindromic substring. So, we increment our
count
.
- This helper function takes
-
Total Count: By calling
expand_around_center
for every possible single-character center (i, i
) and every possible two-character center (i, i+1
), we ensure that all palindromic substrings are found and counted.
The time complexity is O(n^2) because we iterate through each character (n) and for each character, we expand outwards (up to n/2 times). The space complexity is O(1).