Medium

题目描述

给你一个字符串 s 和一个字符 c。返回 s 中以 c 开头且以 c 结尾的子字符串的总数。

示例 1：

输入：s = "abada", c = "a"
输出：6
解释：以 "a" 开头且以 "a" 结尾的子字符串有："a", "aba", "abada", "a", "ada", "a"。

示例 2：

输入：s = "zzz", c = "z"
输出：6
解释：s 中总共有 6 个子字符串，且都以 "z" 开头和结尾。

约束条件：

  • 1 <= s.length <= 10^5
  • s 和 c 仅包含小写英文字母。

提示：

  • 统计字符串 s 中字符 c 的数量，记为 m
  • 我们可以选择两个数字 i 和 j，使得 i <= j 作为子字符串的开始和结束索引。注意 i 和 j 可以相同
  • 答案是 m * (m + 1) / 2

解题思路

解题思路

这道题的核心是理解组合数学的应用。

分析过程：

  1. 观察规律：我们需要找到所有以字符 c 开头和结尾的子字符串。关键洞察是，任意两个字符 c 的位置都可以形成一个有效的子字符串。

  2. 数学转化：

    • 首先统计字符串中字符 c 的出现次数，记为 count
    • 对于每个字符 c 的位置，它可以作为子字符串的起点
    • 它可以与它自己以及后面所有的 c 位置组成有效子字符串

  3. 组合计算：

    • 如果有 count 个字符 c，那么可以选择任意两个位置（包括相同位置）作为子字符串的开始和结束
    • 这相当于从 count 个位置中选择 2 个的组合（允许重复），即 C(count+1, 2)
    • 计算公式为：count * (count + 1) / 2

算法步骤：

  1. 遍历字符串，统计字符 c 的出现次数
  2. 应用组合公式计算结果

这个解法时间复杂度为 O(n)，空间复杂度为 O(1)，是最优解。

代码实现

class Solution {
public:
    long long countSubstrings(string s, char c) {
        long long count = 0;
        for (char ch : s) {
            if (ch == c) {
                count++;
            }
        }
        return count * (count + 1) / 2;
    }
};

class Solution:
    def countSubstrings(self, s: str, c: str) -> int:
        count = s.count(c)
        return count * (count + 1) // 2

public class Solution {
    public long CountSubstrings(string s, char c) {
        long count = 0;
        foreach (char ch in s) {
            if (ch == c) {
                count++;
            }
        }
        return count * (count + 1) / 2;
    }
}

/**
 * @param {string} s
 * @param {character} c
 * @return {number}
 */
var countSubstrings = function(s, c) {
    let count = 0;
    for (let i = 0; i < s.length; i++) {
        if (s[i] === c) {
            count++;
        }
    }
    return count * (count + 1) / 2;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n)
空间复杂度O(1)

其中 n 是字符串 s 的长度。算法只需要遍历一次字符串来统计字符出现次数，然后进行常数时间的数学计算。