难度: Medium
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：s = "abc" 输出：3 解释：三个回文子串: "a", "b", "c"
示例 2：
输入：s = "aaa" 输出：6 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示：
1 <= s.length <= 1000s 由小写英文字母组成运行时间: 34 ms
内存: 16.2 MB
class Solution:
def countSubstrings(self, s: str) -> int:
start = 0
continuous_substrings = []
for i in range(len(s)):
if s[i] != s[start]:
continuous_substrings.append((start, i-1))
start = i
continuous_substrings.append((start, len(s)-1))
res = 0
for i, j in continuous_substrings:
res += (1+(j-i+1)) * (j-i+1) // 2
k = 1
while i-k >= 0 and j+k < len(s):
if s[i-k] == s[j+k]:
res += 1
k += 1
else:
break
return res
这个题解的思路是先找出字符串中所有连续相同字符构成的子串，统计它们的回文子串数量。接着再枚举连续子串的两端，向两边拓展，统计由不同字符构成的回文子串数量。最后将两部分的数量相加得到答案。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def countSubstrings(self, s: str) -> int:
start = 0
continuous_substrings = []
# 找出所有连续相同字符构成的子串
for i in range(len(s)):
if s[i] != s[start]:
continuous_substrings.append((start, i-1))
start = i
continuous_substrings.append((start, len(s)-1))
res = 0
# 统计连续相同字符构成的回文子串数量
for i, j in continuous_substrings:
res += (1+(j-i+1)) * (j-i+1) // 2
# 枚举连续相同字符子串的两端，向两边拓展
k = 1
while i-k >= 0 and j+k < len(s):
if s[i-k] == s[j+k]:
res += 1
k += 1
else:
break
return res
在连续相同字符的子串中，任何长度的子串都自然形成回文子串。例如一个长度为 n 的连续相同字符子串，可以形成 1 个长度为 n 的回文子串、2 个长度为 n-1 的回文子串，以此类推，直到 n 个长度为 1 的回文子串。这个数量可以用等差数列的求和公式计算，即 (1 + n) * n / 2。在这里，n 是连续相同字符的个数，即 (j-i+1)。
在向两边扩展检查回文子串时，每次扩展都是对称的，即从中心点或中心对称的字符对向两端同时扩展。如果在某个点对称的字符不相等，则该点不可能是回文的一部分，因此不需要进一步检查。由于回文的特性是对称的，一旦找到不对称的字符，可以立即断定不是回文，从而不会遗漏。
当在枚举连续相同字符子串的两端并向两边扩展时，如果扩展点的两边的字符相同，则这两个字符可以形成新的回文子串。此时，可以继续扩展，即再向外各移动一位，继续检查下一对字符是否相同，如果仍然相同，则继续形成更大的回文子串，这个过程会持续到找到不相同的字符为止。
连续相同字符的子串处理完后能得到所有完全由相同字符组成的回文子串，但是复合回文子串，即由不同字符组成的回文子串还未被计算。因此，需要单独处理向两边扩展的情况，以便捕捉那些起始于一个固定的连续相同字符子串，但包含其他不同字符的更长回文子串。