What is the core pattern of the problem 'Count the Number of Special Characters II'?

The core pattern involves using hash tables to efficiently track the first occurrence of uppercase and last occurrence of lowercase letters, ensuring the correct ordering.

How do you handle case-sensitive letter counting in this problem?

By using a hash table to store the positions of both lowercase and uppercase occurrences, you can quickly check the order and count special characters.

Can this problem be solved with just string manipulation?

While string manipulation is useful, using a hash table provides a much more efficient solution to track character occurrences and ensure proper ordering.

What is the time complexity of solving the problem?

The time complexity is O(n), where n is the length of the string, as you perform two passes over the string and use a hash table for constant-time lookups.

Are there any edge cases to consider in this problem?

Yes, edge cases include strings with no special characters, strings where characters appear only in one case, and very large strings up to the given length constraint.

#3121

Medium

auto_awesome哈希·表·结合·string

LeetCode 题解工作台

统计特殊字母的数量 II

给你一个字符串 word 。如果 word 中同时出现某个字母 c 的小写形式和大写形式，并且每个小写形式的 c 都出现在第一个大写形式的 c 之前，则称字母 c 是一个特殊字母。返回 word 中特殊字母的数量。示例 1: 输入： word = "aaAbcBC" 输出： 3 解释…

哈希表字符串

题目描述

给你一个字符串 word。如果 word 中同时出现某个字母 c 的小写形式和大写形式，并且每个小写形式的 c 都出现在第一个大写形式的 c 之前，则称字母 c 是一个 特殊字母 。

返回 word 中 特殊字母 的数量。

示例 1:

输入：word = "aaAbcBC"

输出：3

解释：

特殊字母是 'a'、'b' 和 'c'。

示例 2:

输入：word = "abc"

输出：0

解释：

word 中不存在特殊字母。

示例 3:

输入：word = "AbBCab"

输出：0

解释：

word 中不存在特殊字母。

提示：

1 <= word.length <= 2 * 10⁵
word 仅由小写和大写英文字母组成。

lightbulb

解题思路

方法一：哈希表或数组

我们定义两个哈希表或数组 $\textit{first}$ 和 $\textit{last}$ ，用于存储每个字母第一次出现的位置和最后一次出现的位置。

然后我们遍历字符串 $\textit{word}$ ，更新 $\textit{first}$ 和 $\textit{last}$ 。

最后我们遍历所有的小写字母和大写字母，如果 $\textit{last}[a]$ 存在且 $\textit{first}[b]$ 存在且 $\textit{last}[a] < \textit{first}[b]$ ，则说明字母 $a$ 是一个特殊字母，将答案加一。

时间复杂度 $O(n + |\Sigma|)$ ，空间复杂度 $O(|\Sigma|)$ 。其中 $n$ 为字符串 $\textit{word}$ 的长度；而 $|\Sigma|$ 为字符集大小，本题中 $|\Sigma| \leq 128$ 。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def numberOfSpecialChars(self, word: str) -> int:
        first, last = {}, {}
        for i, c in enumerate(word):
            if c not in first:
                first[c] = i
            last[c] = i
        return sum(
            a in last and b in first and last[a] < first[b]
            for a, b in zip(ascii_lowercase, ascii_uppercase)
        )

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
Look for an efficient solution that minimizes both time and space complexity using hash tables.
question_mark
Ensure the candidate recognizes the need for two passes or a similar approach to process both lowercase and uppercase occurrences.
question_mark
Evaluate whether the candidate can effectively balance clarity and optimization in their approach.

warning

常见陷阱

外企场景

error
Failing to account for the proper order of lowercase and uppercase occurrences can lead to incorrect results.
error
Using an inefficient solution that does not utilize a hash table to track positions properly.
error
Not considering edge cases, such as strings with no special characters or strings where characters appear only in one case.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Extend the problem to include numbers or other special characters.
arrow_right_alt
Add a constraint to allow only specific subsets of characters (e.g., only letters A-Z, or only lowercase).
arrow_right_alt
Consider optimizing space usage by using a more space-efficient data structure instead of a hash table.

help

常见问题

外企场景

继续练习

#3120 统计特殊字母的数量 I #3137 K 周期字符串需要的最少操作次数 #3138 同位字符串连接的最小长度