Palindromic Substrings
Problem Statement
Given a string s
, return the number of substrings within s
that are palindromes.
A palindrome is a string that reads the same forward and backward.
Example 1:
Input: s = "abc"Output: 3
Explanation: “a”, “b”, “c”.
Example 2:
Input: s = "aaa"Output: 6
Explanation: “a”, “a”, “a”, “aa”, “aa”, “aaa”. Note that different substrings are counted as different palindromes even if the string contents are the same.
Constraints:
1 <= s.length <= 1000
s
consists of lowercase English letters.
You should aim for a solution as good or better than O(n^2)
time and O(1)
space, where n
is the length of the given string.
Recommended Time and Space Complexity
You should aim for a solution as good or better than O(n^2)
time and O(1)
space, where n
is the length of the given string.
Hint 1
A brute-force solution would be to check if every substring is a palindrome and return the total number of palindromic substrings. This would be an O(n^3)
time solution. Can you think of a better way? Perhaps you should consider thinking in terms of the center of a palindrome.
Hint 2
Iterate over the string with index i
and treat the current character as the center. For this character, try to extend outward to the left and right simultaneously, but only if both characters are equal. At each iteration, we increment the count of palindromes. How would you implement this? Can you consider both cases: even-length and odd-length palindromes?
Hint 3
Initialize a variable res
to track the count of palindromes. At each index, create an odd-length palindrome starting at that index extending outward from both its left and right indices, i.e., i - 1
and i + 1
. How can you find the even-length palindrome for this index?
Hint 4
For an even-length palindrome, consider expanding from indices i
and i + 1
. This two-pointer approach, extending from the center of the palindrome, will help find all palindromic substrings in the given string and return its count.
Solution
Brute Force
def count_substrings(s: str) -> int: res = 0
for i in range(len(s)): for j in range(i, len(s)): l, r = i, j while l < r and s[l] == s[r]: l += 1 r -= 1 res += (l >= r)
return res
Time complexity: O(n^3)
Space complexity: O(1)
Dynamic Programming
def count_substrings(s: str) -> int: n, res = len(s), 0 dp = [[False] * n for _ in range(n)]
for i in range(n - 1, -1, -1): for j in range(i, n): if s[i] == s[j] and (j - i <= 2 or dp[i + 1][j - 1]): dp[i][j] = True res += 1
return res
Time complexity: O(n^2)
Space complexity: O(n^2)
Two Pointers
def count_substrings(s: str) -> int: res = 0
for i in range(len(s)): # odd length l, r = i, i while l >= 0 and r < len(s) and s[l] == s[r]: res += 1 l -= 1 r += 1
# even length l, r = i, i + 1 while l >= 0 and r < len(s) and s[l] == s[r]: res += 1 l -= 1 r += 1
return res
Time complexity: O(n^2)
Space complexity: O(1)
Two Pointers (Optimal)
def count_substrings(s: str) -> int: res = 0
for i in range(len(s)): res += count_palindromes(s, i, i) res += count_palindromes(s, i, i + 1) return res
def count_palindromes(s, l, r): res = 0 while l >= 0 and r < len(s) and s[l] == s[r]: res += 1 l -= 1 r += 1 return res
Time complexity: O(n^2)
Space complexity: O(1)
Manacher’s Algorithm
def count_substrings(s: str) -> int:
def manacher(s): t = '#' + '#'.join(s) + '#' n = len(t) p = [0] * n l, r = 0, 0 for i in range(n): p[i] = min(r - i, p[l + (r - i)]) if i < r else 0 while (i + p[i] + 1 < n and i - p[i] - 1 >= 0 and t[i + p[i] + 1] == t[i - p[i] - 1]): p[i] += 1 if i + p[i] > r: l, r = i - p[i], i + p[i] return p
p = manacher(s) res = 0 for i in p: res += (i + 1) // 2 return res
Time complexity: O(n)
Space complexity: O(n)