Palindromic Substrings
Given a string, write a function to return the count of all possible palindromic substrings. A palindromic substring is a substring that reads the same backward as forward.
Constraints:
- 1 <= s.length <= 1000
- s consists of lowercase English letters.
Examples:
Input: "abc"
Output: 3
Explanation: Three palindromic substrings: "a", "b", "c".
Input: "aaa"
Output: 6
Explanation: Six palindromic substrings: "a", "a", "a", "aa", "aa", "aaa".
Solutions
Expand Around Center
Time: O(n^2)Space: O(1)
The approach is to expand around the center of the palindrome. We consider each character as the center of a potential palindrome and expand outwards to count the number of palindromic substrings. We also consider the case where the center of the palindrome is between two characters.
def countSubstrings(s:
str) -> int:
count = 0
for i in range(len(s)):
count += count_palindromes(s, i, i)
count += count_palindromes(s, i, i + 1)
return count
def count_palindromes(s:
str, left:
int, right:
int) -> int:
count = 0
while left >= 0 and right < len(s) and s[left] == s[right]:
count += 1
left -= 1
right += 1
return countFollow-up:
How would you optimize the solution to handle very large strings?
