How can I count substrings that start and end with a specific character?

Count the number of occurrences of the character in the string. The number of valid substrings can be calculated with the formula `m * (m - 1) / 2 + m`.

What is the time complexity of the solution?

The time complexity is O(n), where n is the length of the string, because we only need to count the occurrences of the character.

What are the common mistakes in solving the Count Substrings Starting and Ending with Given Character problem?

Common mistakes include forgetting to include substrings of length 1, misapplying the formula for counting, or trying to check all substrings directly.

Can the solution be optimized further?

No, the solution is already optimal with O(n) time complexity for counting occurrences. It does not require checking all possible substrings.

How does the formula for counting substrings work?

The formula `m * (m - 1) / 2 + m` counts how many ways you can pick two positions from `m` occurrences and adds `m` for single-character substrings.

#3084

Medium

auto_awesome数学·string

LeetCode 题解工作台

统计以给定字符开头和结尾的子字符串总数

给你一个字符串 s 和一个字符 c 。返回在字符串 s 中并且以 c 字符开头和结尾的非空子字符串的总数。示例 1：输入： s = "abada", c = "a" 输出： 6 解释：以 "a" 开头和结尾的子字符串有： " a bada" 、 " aba da" 、 " abada " …

数学字符串计数

题目描述

给你一个字符串 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 <= 10⁵
s 和 c 均由小写英文字母组成。

lightbulb

解题思路

方法一：数学

我们可以先统计字符串 $s$ 中字符 $c$ 的个数，记为 $cnt$ 。

每个 $c$ 字符可以单独作为一个子字符串，所以有 $cnt$ 个子字符串满足条件。每个 $c$ 字符可以和其他 $c$ 字符组成一个满足条件的子字符串，所以有 $\frac{cnt \times (cnt - 1)}{2}$ 个子字符串满足条件。

所以答案为 $cnt + \frac{cnt \times (cnt - 1)}{2}$ 。

时间复杂度 $O(n)$ ，其中 $n$ 为字符串 $s$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate counts occurrences correctly and applies the mathematical formula properly.
question_mark
Look for efficient handling of large strings, as the length can reach 10^5.
question_mark
Assess if the candidate recognizes the need to avoid brute force approaches like checking all possible substrings.

warning

常见陷阱

外企场景

error
Forgetting to include substrings of length 1 in the calculation.
error
Confusing the mathematical formula for substring counting, especially how to handle the pairings of occurrences.
error
Overcomplicating the problem by trying to find substrings directly, instead of focusing on character occurrences.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to allow multiple characters instead of just one to be checked at the beginning and end.
arrow_right_alt
Extend the problem to handle strings with upper and lowercase characters or other special characters.
arrow_right_alt
Change the task to count substrings that start with `c` and end with a different character.

help

常见问题

外企场景

继续练习

#3335 字符串转换后的长度 I #3337 字符串转换后的长度 II #3443 K 次修改后的最大曼哈顿距离