Hard

题目描述

定义一个函数 countUniqueChars(s)，它返回字符串 s 中唯一字符的数量。

例如，如果 s = "LEETCODE"，那么 “L”、“T”、“C”、“O”、“D” 是唯一字符，因为它们在 s 中只出现一次，所以 countUniqueChars(s) = 5。

给定一个字符串 s，返回所有 s 的子串 t 的 countUniqueChars(t) 的总和。测试用例保证答案在 32 位整数范围内。

注意一些子串可能会重复，在这种情况下你需要计算重复的子串。

示例 1：

输入：s = "ABC"
输出：10
解释：所有可能的子串为："A","B","C","AB","BC" 和 "ABC"。
每个子串都只由唯一字母组成。
所有子串长度的和为 1 + 1 + 1 + 2 + 2 + 3 = 10

示例 2：

输入：s = "ABA"
输出：8
解释：与示例 1 相同，除了 countUniqueChars("ABA") = 1。

示例 3：

输入：s = "LEETCODE"
输出：92

提示：

  • 1 <= s.length <= 10^5
  • s 只包含大写英文字母。

解题思路

这道题要求计算所有子串中唯一字符数量的总和。直接枚举所有子串会导致 O(n³) 的时间复杂度，无法通过。

核心思路：贡献度计算

我们换个思路，考虑每个字符对最终结果的贡献。对于字符串中的每个字符，我们计算它在多少个子串中是唯一字符，然后将所有贡献相加。

对于位置 i 的字符 s[i]，它在子串中是唯一字符的条件是：

  1. 子串必须包含位置 i
  2. 子串中不能包含其他相同的字符

为了计算字符 s[i] 的贡献，我们需要找到：

  • left：s[i] 左边最近的相同字符位置（如果没有则为 -1）
  • right：s[i] 右边最近的相同字符位置（如果没有则为 n）

这样，包含 s[i] 且 s[i] 在其中唯一的子串数量为：(i - left) * (right - i)

算法步骤：

  1. 使用哈希表记录每个字符上次出现的位置
  2. 遍历字符串，对每个字符计算其贡献度
  3. 更新字符的最后出现位置

时间复杂度为 O(n)，空间复杂度为 O(1)（因为只有26个大写字母）。

代码实现

class Solution {
public:
    int uniqueLetterString(string s) {
        int n = s.length();
        vector<int> lastPos(26, -1);  // 每个字符上次出现的位置
        vector<int> secondLastPos(26, -1);  // 每个字符上上次出现的位置
        int result = 0;
        
        for (int i = 0; i < n; i++) {
            int c = s[i] - 'A';
            int left = lastPos[c];  // 左边最近的相同字符位置
            int farLeft = secondLastPos[c];  // 左边第二近的相同字符位置
            
            // 计算当前字符的贡献
            result += (i - left) * (left - farLeft);
            
            // 更新位置信息
            secondLastPos[c] = lastPos[c];
            lastPos[c] = i;
        }
        
        // 处理每个字符的最后贡献
        for (int c = 0; c < 26; c++) {
            int left = lastPos[c];
            int farLeft = secondLastPos[c];
            if (left != -1) {
                result += (n - left) * (left - farLeft);
            }
        }
        
        return result;
    }
};

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        n = len(s)
        last_pos = [-1] * 26  # 每个字符上次出现的位置
        second_last_pos = [-1] * 26  # 每个字符上上次出现的位置
        result = 0
        
        for i in range(n):
            c = ord(s[i]) - ord('A')
            left = last_pos[c]  # 左边最近的相同字符位置
            far_left = second_last_pos[c]  # 左边第二近的相同字符位置
            
            # 计算当前字符的贡献
            result += (i - left) * (left - far_left)
            
            # 更新位置信息
            second_last_pos[c] = last_pos[c]
            last_pos[c] = i
        
        # 处理每个字符的最后贡献
        for c in range(26):
            left = last_pos[c]
            far_left = second_last_pos[c]
            if left != -1:
                result += (n - left) * (left - far_left)
        
        return result

public class Solution {
    public int UniqueLetterString(string s) {
        int n = s.Length;
        int[] lastPos = new int[26];
        int[] secondLastPos = new int[26];
        
        // 初始化为-1
        for (int i = 0; i < 26; i++) {
            lastPos[i] = -1;
            secondLastPos[i] = -1;
        }
        
        int result = 0;
        
        for (int i = 0; i < n; i++) {
            int c = s[i] - 'A';
            int left = lastPos[c];  // 左边最近的相同字符位置
            int farLeft = secondLastPos[c];  // 左边第二近的相同字符位置
            
            // 计算当前字符的贡献
            result += (i - left) * (left - farLeft);
            
            // 更新位置信息
            secondLastPos[c] = lastPos[c];
            lastPos[c] = i;
        }
        
        // 处理每个字符的最后贡献
        for (int c = 0; c < 26; c++) {
            int left = lastPos[c];
            int farLeft = secondLastPos[c];
            if (left != -1) {
                result += (n - left) * (left - farLeft);
            }
        }
        
        return result;
    }
}

var uniqueLetterString = function(s) {
    const n = s.length;
    const lastPos = new Array(26).fill(-1);  // 每个字符上次出现的位置
    const secondLastPos = new Array(26).fill(-1);  // 每个字符上上次出现的位置
    let result = 0;
    
    for (let i = 0; i < n; i++) {
        const c = s.charCodeAt(i) - 65;  // 'A'.charCodeAt(0) = 65
        const left = lastPos[c];  // 左边最近的相同字符位置
        const farLeft = secondLastPos[c];  // 左边第二近的相同字符位置
        
        // 计算当前字符的贡献
        result += (i - left) * (left - farLeft);
        
        // 更新位置信息
        secondLastPos[c] = lastPos[c];
        lastPos[c] = i;
    }
    
    // 处理每个字符的最后贡献
    for (let c = 0; c < 26; c++) {
        const left = lastPos[c];
        const farLeft = secondLastPos[c];
        if (left !== -1) {
            result += (n - left) * (left - farLeft);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

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

其中 n 是字符串的长度。时间复杂度为 O(n) 因为只需要遍历字符串一次，空间复杂度为 O(1) 因为只使用了固定大小的数组来存储 26 个字母的位置信息。

相关题目