Medium

题目描述

给你一个字符串 word。如果一个字母 c 同时以小写和大写形式出现在 word 中，并且每一个小写字母 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^5
  • word 仅由小写和大写英文字母组成

提示：

  • 对于每个字符 c，存储其大写字母的第一次出现位置和小写字母的最后一次出现位置。

解题思路

这道题要求找出满足以下条件的特殊字母：

  1. 字母同时有大小写形式出现
  2. 所有小写字母都出现在第一个大写字母之前

核心思路：

  • 遍历字符串，记录每个字母的小写形式最后出现位置和大写形式第一次出现位置
  • 对于每个字母，检查是否同时存在大小写形式，且小写最后位置 < 大写第一次位置

解法分析：

  1. 两次遍历法（推荐）：第一次记录小写最后位置，第二次记录大写第一次位置并判断
  2. 一次遍历法：同时维护两个数组，但需要处理边界情况更复杂

算法步骤：

  1. 初始化两个数组记录位置信息（-1表示未出现）
  2. 第一次遍历记录所有小写字母的最后出现位置
  3. 第二次遍历记录大写字母第一次出现位置，同时检查特殊条件
  4. 统计满足条件的字母数量

时间复杂度为 O(n)，空间复杂度为 O(1)（固定26个字母）。

代码实现

class Solution {
public:
    int numberOfSpecialChars(string word) {
        vector<int> lastLower(26, -1);
        vector<int> firstUpper(26, -1);
        
        // 记录小写字母最后出现位置
        for (int i = 0; i < word.length(); i++) {
            if (word[i] >= 'a' && word[i] <= 'z') {
                lastLower[word[i] - 'a'] = i;
            }
        }
        
        // 记录大写字母第一次出现位置
        for (int i = 0; i < word.length(); i++) {
            if (word[i] >= 'A' && word[i] <= 'Z') {
                int idx = word[i] - 'A';
                if (firstUpper[idx] == -1) {
                    firstUpper[idx] = i;
                }
            }
        }
        
        int count = 0;
        for (int i = 0; i < 26; i++) {
            if (lastLower[i] != -1 && firstUpper[i] != -1 && 
                lastLower[i] < firstUpper[i]) {
                count++;
            }
        }
        
        return count;
    }
};

class Solution:
    def numberOfSpecialChars(self, word: str) -> int:
        last_lower = [-1] * 26
        first_upper = [-1] * 26
        
        # 记录小写字母最后出现位置
        for i, c in enumerate(word):
            if 'a' <= c <= 'z':
                last_lower[ord(c) - ord('a')] = i
        
        # 记录大写字母第一次出现位置
        for i, c in enumerate(word):
            if 'A' <= c <= 'Z':
                idx = ord(c) - ord('A')
                if first_upper[idx] == -1:
                    first_upper[idx] = i
        
        count = 0
        for i in range(26):
            if (last_lower[i] != -1 and first_upper[i] != -1 and 
                last_lower[i] < first_upper[i]):
                count += 1
        
        return count

public class Solution {
    public int NumberOfSpecialChars(string word) {
        int[] lastLower = new int[26];
        int[] firstUpper = new int[26];
        
        // 初始化为-1
        for (int i = 0; i < 26; i++) {
            lastLower[i] = -1;
            firstUpper[i] = -1;
        }
        
        // 记录小写字母最后出现位置
        for (int i = 0; i < word.Length; i++) {
            if (word[i] >= 'a' && word[i] <= 'z') {
                lastLower[word[i] - 'a'] = i;
            }
        }
        
        // 记录大写字母第一次出现位置
        for (int i = 0; i < word.Length; i++) {
            if (word[i] >= 'A' && word[i] <= 'Z') {
                int idx = word[i] - 'A';
                if (firstUpper[idx] == -1) {
                    firstUpper[idx] = i;
                }
            }
        }
        
        int count = 0;
        for (int i = 0; i < 26; i++) {
            if (lastLower[i] != -1 && firstUpper[i] != -1 && 
                lastLower[i] < firstUpper[i]) {
                count++;
            }
        }
        
        return count;
    }
}

/**
 * @param {string} word
 * @return {number}
 */
var numberOfSpecialChars = function(word) {
    const lastLower = new Map();
    const firstUpper = new Map();
    
    for (let i = 0; i < word.length; i++) {
        const char = word[i];
        if (char >= 'a' && char <= 'z') {
            lastLower.set(char, i);
        } else {
            const lowerChar = char.toLowerCase();
            if (!firstUpper.has(lowerChar)) {
                firstUpper.set(lowerChar, i);
            }
        }
    }
    
    let count = 0;
    for (const [char, lastPos] of lastLower) {
        if (firstUpper.has(char) && lastPos < firstUpper.get(char)) {
            count++;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

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

说明：

  • 时间复杂度：需要遍历字符串两次，每次 O(n)，总体为 O(n)
  • 空间复杂度：使用两个固定大小为26的数组，为 O(1)

相关题目