https://leetcode.com/problems/palindromic-substrings/
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”.
Constraints:
1 <= s.length <= 1000
s consists of lowercase English letters.
- code
class Solution:
def countSubstrings(self, s: str) -> int:
def expand(l, r):
cur_ct = 0
while l >= 0 and r < len(s):
if s[l] != s[r]:
break
cur_ct += 1
l -= 1
r += 1
return cur_ct
count = 0
for i in range(len(s)):
count += expand(i, i)
if i + 1 < len(s) and s[i] == s[i + 1]:
count += expand(i, i + 1)
return count