Palindromic substrings#
Practice Link#
Description#
- Given a string, your task is to count how many palindromic substrings in this string.
- The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.
Note:
- The input string length won’t exceed 1000.
Examples#
1Input: "abc"
2Output: 3
3Explanation: Three palindromic strings: "a", "b", "c".1Input: "aaa"
2Output: 6
3Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".Python Solution#
1class Solution(object):
2 # Let N be the length of the string. The middle of the palindrome could be in one of 2N - 1 positions: either at letter or between two letters.
3 # For each center, let's count all the palindromes that have this center. Notice that if [a, b] is a palindromic interval (meaning S[a], S[a+1], ..., S[b] is a palindrome), then [a+1, b-1] is one too.
4 # Algorithm
5 # For each possible palindrome center,
6 # let's expand our candidate palindrome on the interval [left, right] as long as we can.
7 # The condition for expanding is left >= 0 and right < N and S[left] == S[right].
8 # That means we want to count a new palindrome S[left], S[left+1], ..., S[right].
9 def countSubstrings(self, S):
10 N = len(S)
11 ans = 0
12 for center in range(2 * N - 1):
13 left = center / 2
14 right = left + center % 2
15 while left >= 0 and right < N and S[left] == S[right]:
16 ans += 1
17 left -= 1
18 right += 1
19 return ans