难度: Medium
给你一个字符串 s 和一个字符 c 。返回在字符串 s 中并且以 c 字符开头和结尾的非空子字符串的总数。
示例 1：
输入：s = "abada", c = "a"
输出：6
解释：以 "a" 开头和结尾的子字符串有： "abada"、"abada"、"abada"、"abada"、"abada"、"abada"。
示例 2：
输入：s = "zzz", c = "z"
输出：6
解释：字符串 s 中总共有 6 个子字符串，并且它们都以 "z" 开头和结尾。
提示：
1 <= s.length <= 105s 和 c 均由小写英文字母组成。运行时间: 21 ms
内存: 16.5 MB
class Solution: def countSubstrings(self, s, c): n = s.count(c) return n * (n + 1) // 2
该题解的核心思路是首先统计字符 c 在字符串 s 中出现的次数 n。然后利用组合数学的知识，计算出所有以字符 c 开头和结尾的子字符串的数量。如果 c 在 s 中出现n次，那么任选两个位置组成的子字符串都将以 c 作为开头和结尾，这样的选择方式共有 C(n, 2) = n*(n-1)/2 种。此外，每个单独的字符 c 本身也是一个符合条件的子字符串，因此总数还要加上 n，即总数为 n*(n+1)/2。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution: def countSubstrings(self, s, c): # 统计字符 c 在字符串 s 中的出现次数 n = s.count(c) # 使用组合数学原理计算所有以 c 为开头和结尾的子字符串的数量 return n * (n + 1) // 2
组合公式 C(n, 2) 用于计算从 n 个元素中任选两个元素的组合方式数量，这里的 n 个元素是字符 c 在字符串 s 中的每次出现。当我们选择两个 c 字符，一个作为子字符串的开头，另一个作为结尾时，这两个位置之间的任何字符都是子字符串的一部分，因此 C(n, 2) 计算了所有可能的子字符串（长度至少为 2）的数量。加上 n 是因为每个单独的字符 c 也算作一个长度为 1 的子字符串。这种计算方式简洁且直接反映了问题的组合本质，是最自然的计算方法。
在字符串非常长的情况下，使用 s.count(c) 已经是计算字符 c 出现次数的高效方法之一，因为它是一个线性时间复杂度的操作，即 O(n)，其中 n 是字符串 s 的长度。尽管如此，如果处理的是超大数据量或需要重复查询多个字符的频次，可以考虑一次性遍历字符串统计所有字符的出现频次，将结果存储在哈希表中，以后每次查询任何字符的频次都可以在常数时间 O(1) 内完成。这种方法前期需要一次遍历，但可以显著加快后续的查询速度。
如果字符 c 在字符串 s 中一次都没有出现，那么 n（c 的出现次数）将为 0。根据公式 n*(n+1)/2，当 n 为 0 时，计算结果也是 0。这表示没有任何子字符串以 c 为开头和结尾，这是符合逻辑的结果。因此，当前实现在处理 c 不出现在 s 中的情况下是正确的，它正确地返回了 0。