3121.统计特殊字母的数量 II：状态机

【LetMeFly】3121.统计特殊字母的数量 II：状态机

力扣题目链接：https://leetcode.cn/problems/count-the-number-of-special-characters-ii/

给你一个字符串 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 * 105
• word 仅由小写和大写英文字母组成。

解题方法：状态机

对于每种字母而言，一共有几种状态？

状态	标记
初始状态	NONE
只遇到了小写字母	SMALL
遇到过小写字母且在此之后只遇到了大写字母	OK
此字母状态不合法	CANNOT

遍历字符串，对于第$i$个字母：

• 如果其状态是NONE：

  • 如果这个字母是小写，则转为SMALL
  • 否则不合法，转为CANNOT

• 如果其状态是SMALL:

  • 如果这个字母是大写，则这个字母到目前为止满足条件，转为OK，答案数量加一

• 如果其状态是OK：

  • 如果这个字母是小写，则大写后出现小写不合法，转为CANNOT，答案数量减一

• 否则（状态已经是CANNOT），不用管了，反正这个字母没希望了

以上。

• 时间复杂度$O(len(word))$
• 空间复杂度$O(C)$，其中$C=26$

AC代码

C++

/*
 * @LastEditTime: 2026-05-27 22:33:20
 */
enum State {
    NONE,
    SMALL,
    OK,
    CANNOT,
};

class Solution {
public:
    int numberOfSpecialChars(string word) {
        State state[26];
        int ans = 0;
        for (char c : word) {
            bool small = 'a' <= c && c <= 'z';
            int idx = small ? c - 'a' : c - 'A';
            switch (state[idx]) {
            case NONE:
                state[idx] = small ? SMALL : CANNOT;
                break;
            case SMALL:
                if (!small) {
                    state[idx] = OK;
                    ans++;
                }
                break;
            case OK:
                if (small) {
                    state[idx] = CANNOT;
                    ans--;
                }
                break;
            }
        }
        return ans;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源