统计子串中的唯一字符

题目链接

统计子串中的唯一字符

题目描述

注意

• s 只包含大写英文字符
• 题目中表达的意思是统计字符串s以及其所有子字符串的所有唯一字符的个数，在不同的子字符串中的唯一字符可能是相同的

解答思路

• 在理解题目意思后，初始按照题目的意思多重循环根据长度找到所有的子字符串以及对应的唯一字符，这样做可以得到正确结果，但是时间复杂度极大，当数据量增多时会超出时间限制
• 参照题解了解到应该计算的是任意某个位置的字符对整个字符串的贡献，也就是其在所有子字符串的组合中是唯一字符的组合数。
• 而贡献的计算又有一个规律：假定某个字符出现在字符串的位置j，该字符上一次出现在字符串的位置i（如果在其之前没有则设置为-1），该字符下一次出现在字符串的位置k（如果在其之后没有则设为s.length()），则该处的字符对所有子字符串组合的唯一字符的贡献为(j - i) * (k - j)（注意计算得到的并不是该字符对整个字符串的贡献，而是该位置处的字符对整个字符串的贡献）
• (j - i) * (k - j)也就是包含该位置处的元素时且能作为唯一字符的所有子字符串的排列组合，例如LEETCODE中第一个E出现的位置为1，其前一个E出现的位置则为-1，其后一个E出现的位置为2，则该位置处的E的贡献为(1-(-1)) * (2-1)=2，也就是"LE"和"E"两种

代码

class Solution {
    public int uniqueLetterString(String s) {
        int res = 0;
        // 存储字符串中字符以及其位置信息
        Map<Character, List<Integer>> map = new HashMap<>();
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 如果该字符是第一次被访问到，则其前方没有相同元素，即位置为-1
            if(!map.containsKey(c)) {
                map.put(c, new ArrayList<>());
                map.get(c).add(-1);
            }
            map.get(c).add(i);
        }

        for(Character key : map.keySet()) {
            List<Integer> list = map.get(key);
            // 最后一个元素后方无元素，即位置为s.length()
            list.add(s.length());
            for(int i = 1; i < list.size() - 1; i++) {
                res += (list.get(i) - list.get(i - 1)) * (list.get(i + 1) - list.get(i));
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

关键点

• 使用一个Map存储字符串中字符以及其位置信息，其中key为字符的值，value为一个List保存了该字符在整个字符串中所有出现的位置
• 理解任意一个位置处的字符对整个字符串的贡献的含义以及计算方法，以及这样计算贡献的原理