统计子串中的唯一字符
我们定义了一个函数 countUniqueChars(s) 来统计字符串 s 中的唯一字符，并返回唯一字符的个数。
例如：s = “LEETCODE” ，则其中 “L”, “T”,”C”,”O”,”D” 都是唯一字符，因为它们只出现一次，所以 countUniqueChars(s) = 5 。
本题将会给你一个字符串 s ，我们需要返回 countUniqueChars(t) 的总和，其中 t 是 s 的子字符串。输入用例保证返回值为 32 位整数。
注意，某些子字符串可能是重复的，但你统计时也必须算上这些重复的子字符串（也就是说，你必须统计 s 的所有子字符串中的唯一字符）。
示例 1：
输入: s = "ABC"
输出: 10
解释: 所有可能的子串为："A","B","C","AB","BC" 和 "ABC"。
其中，每一个子串都由独特字符构成。
所以其长度总和为：1 + 1 + 1 + 2 + 2 + 3 = 10
示例 2：
输入: s = "ABA"
输出: 8
解释: 除了 countUniqueChars("ABA") = 1 之外，其余与示例 1 相同。
示例 3：
输入：s = "LEETCODE"
输出：92
提示：
- $1 <= s.length <= 10^5$
- s 只包含大写英文字符
读题
题目中定义了一个方法countUniqueChars(s)，这个方法返回字符串s中只出现过一次的字符数量——称之为独特字符的总量。
然后，题目要求对于给定的一个长度[0,$10^5$]的字符串，求出该字符串的每个子串的独特字符的数量，并将其累加。
解题
思路1：
- 实现
countUniqueChars - 累加
代码：
class Solution {
public int uniqueLetterString(String s) {
// 第一步 枚举s的所有子串
// 统计每个子串的独特字符的个数，累加
// 长度为n的子串的个数是：1*n + (n-1)*2 + ..+ n*1
// 枚举分割子串
int sum = 0;
for (int i = 1;i <= s.length();i++) {
// String 的substring方法，是[)区间的
for (int start = 0;start < s.length() - i + 1;start++) {
sum += countUniqueChars(s.substring(start,start+i));
}
}
return sum;
}
public int countUniqueChars(String t) {
int[] chars = new int[26];
for (int i = 0; i < t.length(); i++) {
char c = t.charAt(i);
chars[(int)c - (int)'A']++;
}
int sum = 0;
for (int i = 0;i < 26;i ++) {
if (chars[i] == 1) {
sum++;
}
}
return sum;
}
}
问题：超时了。
优化：
- 问题分解：由于字母总数位26，字符串长度超过26，必定有重复值
- 空间换时间
class Solution {
public int uniqueLetterString(String s) {
// 第一步 枚举s的所有子串
// 统计每个子串的独特字符的个数，累加
// 长度为n的子串的个数是：1*n + (n-1)*2 + ..+ n*1
// 用map存储已经处理过的，优化时间复杂度
Map<String,Integer> counted = new HashMap<>();
// 枚举分割子串
int sum = 0;
for (int i = 1;i <= s.length();i++) {
// String 的substring方法，是[)区间的
for (int start = 0;start < s.length() - i + 1;start++) {
String subs = s.substring(start,start+i);
if (counted.containsKey(subs)){
sum += counted.get(subs);
} else {
int r = countUniqueChars(subs);
counted.put(subs,r);
sum += r;
}
}
}
return sum;
}
public int countUniqueChars(String t) {
if (t.length() == 1) {
return 1;
}
int[] chars = new int[26];
for (int i = 0; i < t.length(); i++) {
char c = t.charAt(i);
chars[(int)c - (int)'A']++;
}
int sum = 0;
for (int i = 0;i < 26;i ++) {
if (chars[i] == 1) {
sum++;
}
}
return sum;
}
}
还是超时，这种思路已经行不通了！！！
思路2
s的每个子串的独立字符数量的累加 <==> 字符就26种，每种有多个下标，两个下标之间的子串的长度。
统计字符串s中每个位置的字符，同一个字符出现的各个位置（位置总数为的s长度），然后遍历这些位置。
遍历这些位置，用数学公式计算出组合数量，由于每个字符的组合数量都会计算，这种计算方式算是一种取巧的组合计算方式。
本质：移除重复字符的数量，直接计算非重复字符的组合。
class Solution {
public int uniqueLetterString(String s) {
// 统计每个字符出现的位置
Map<Character,List<Integer>> index = new HashMap<Character,List<Integer>>();
for (int i = 0;i < s.length();i++) {
char c = s.charAt(i);
if (!index.containsKey(c)) {
index.put(c,new ArrayList<Integer>());
index.get(c).add(-1);// 这里的意思是每个字符自己贡献1
}
index.get(c).add(i);
}
int res = 0;
for (Map.Entry<Character, List<Integer>> entry : index.entrySet()) {
// 计算每个单个字符的可以统计的总数量
List<Integer> arr = entry.getValue();
arr.add(s.length());// 这里的意思是，每个字母的最后一个index需要和整个s的最后一个位置计算数量
for (int i = 1;i < arr.size() - 1;i++) {
// 每个位置和前后位置相剪，然后相乘。这个计算移除了重复字符的数量
res += (arr.get(i) - arr.get(i - 1)) * (arr.get(i + 1) - arr.get(i));
}
}
return res;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
