对于 LeetCode 828 题「统计子串中唯一的字符」，常见的解法是使用贡献法（也称独立计算法），即考虑每个字符在哪些子串中可以作为唯一字符出现，然后将所有字符的贡献相加。

核心思路

对于字符串 s 中的某个位置 i 的字符 c = s.charAt(i)，它只对满足以下条件的子串有贡献：

· 子串包含位置 i。
· 在子串中，字符 c 只出现一次。

换句话说，我们需要找到字符 c 在 i 左边最近的一个相同字符的位置 left，以及在右边最近的一个相同字符的位置 right。那么，所有以 i 为唯一 c 的子串，其左端点可以在 (left, i] 区间内选择，右端点可以在 [i, right) 区间内选择。这样的子串个数为：

(i - left) * (right - i)

其中：

· left 初始为 -1（表示左边没有相同字符）。
· right 初始为 n（表示右边没有相同字符）。

算法步骤

1. 从左到右遍历字符串，记录每个位置左边最近相同字符的位置，存入数组 left。
2. 从右到左遍历字符串，记录每个位置右边最近相同字符的位置，存入数组 right。
3. 遍历每个位置 i，计算贡献值 (i - left[i]) * (right[i] - i)，并累加到结果中。

复杂度

· 时间复杂度：O(n)，只需遍历三次字符串。
· 空间复杂度：O(n)，用于存储 left 和 right 数组（如果使用哈希表记录字符最近位置，空间可视为 O(1) 因为字符集有限）。

Java 代码实现

class Solution {
    public int uniqueLetterString(String s) {
        int n = s.length();
        int[] left = new int[n];
        int[] right = new int[n];
        int[] lastIndex = new int[26]; // 记录每个字符上次出现的位置
        Arrays.fill(lastIndex, -1);
        
        // 计算 left 数组
        for (int i = 0; i < n; i++) {
            left[i] = lastIndex[s.charAt(i) - 'A'];
            lastIndex[s.charAt(i) - 'A'] = i;
        }
        
        // 重置 lastIndex 用于计算 right 数组
        Arrays.fill(lastIndex, n);
        for (int i = n - 1; i >= 0; i--) {
            right[i] = lastIndex[s.charAt(i) - 'A'];
            lastIndex[s.charAt(i) - 'A'] = i;
        }
        
        long ans = 0;
        for (int i = 0; i < n; i++) {
            ans += (long) (i - left[i]) * (right[i] - i);
        }
        return (int) ans;
    }
}

示例

以 s = “ABC” 为例：

· 对于 i=0 (‘A’)：left=-1, right=3 → (0-(-1))(3-0)=13=3
· 对于 i=1 (‘B’)：left=-1, right=3 → (1-(-1))(3-1)=22=4
· 对于 i=2 (‘C’)：left=-1, right=3 → (2-(-1))(3-2)=31=3
总和 = 3+4+3 = 10，符合预期。

注意事项

· 题目中字符可能为大写字母，若包含其他字符可改用 HashMap 存储。
· 结果可能较大，使用 long 累加避免溢出，最后转回 int 返回。