一、题目
我们定义了一个函数 countUniqueChars(s) 来统计字符串 s 中的唯一字符，并返回唯一字符的个数。
例如：s = "LEETCODE" ，则其中 "L", "T","C","O","D" 都是唯一字符，因为它们只出现一次，所以 countUniqueChars(s) = 5 。
本题将会给你一个字符串 s ，我们需要返回 countUniqueChars(t) 的总和，其中 t 是 s 的子字符串。输入用例保证返回值为 32 位整数。
注意，某些子字符串可能是重复的，但你统计时也必须算上这些重复的子字符串（也就是说，你必须统计 s 的所有子字符串中的唯一字符）。
二、示例
2.1> 示例 1：
【输入】 s = "ABC"
【输出】 10
【解释】 所有可能的子串为："A","B","C","AB","BC" 和 "ABC"。其中，每一个子串都由独特字符构成。所以其长度总和为：1 + 1 + 1 + 2 + 2 + 3 = 10
2.2> 示例 2：
【输入】 s = "ABA"
【输出】 8
【解释】 除了 countUniqueChars("ABA") = 1 之外，其余与示例 1 相同。
2.3> 示例 3：
【输入】s = "LEETCODE"
【输出】92
提示：
-
1<= s.length <=10^5 -
s只包含大写英文字符
三、解题思路
当初看这道题的时候，着实被题目描述弄迷糊了。看了好几遍中文/英文题目描述和示例，才看明白。其实意思就是给一个字符串s，先将s分解为N个子串，然后再针对每个子串进行计算，计算方式是：子串中仅出现1次的字符，算作1，出现多次的字符，则不纳入计算，然后将结果相加。当然，这是一个子串的计算方式，我们拆分出N的子串，就都要这么计算一下，最终N个子串的总结果，就是本题的返回值。
请看下图，我们以s=“ABCD”为例，首先，可以将其拆分为10个子串（以“A”为基准的4个子串；以“B”为基准的3个子串；以“C”为基准的2个子串；以“D”为基准的1个子串；），那么由于s字符串中的字符都是彼此不重复的，所以，总结果其实就是“A”、“B”、“C”、“D”这个四个字符在所有10个子串中出现的次数之和，即：A出现4次 + A出现6次 + A出现6次 + A出现4次 = 20。
通过上面的例子，我们将问题转换为某个字符在所以子串中出现的个数问题了。那么，针对这个问题，其实有3种情况：
情况1：字符是“头元素”，那么出现次数可以通过：
数组长度 - 元素下标位置来计算出来。
情况2：字符是“尾元素”，那么出现次数可以通过：元素下标位置 - (-1)来计算出来。
情况3：字符是“中间元素”，那么出现次数可以通过：(元素下标位置 - (-1)) * (数组长度 - 元素下标位置)来计算出来。
图片
那么前面我们是针对于字符串中字符不重复的情况来看的，下面我们再来看一下有重复字符的情况。其实，针对于这种情况，就产生了区间的概念。因为我们上面进行统计的时候，都是针对于某一区间内这个元素是唯一的，所以，如果发生了重复字符，我们就需要将其拆分为多个区间。以下图s="ABCB"为例，当我们要统计元素“B”的时候，由于发生了重复的情况，所以，我们要将其拆分为：
当B的下标=1的时候，它唯一的区间是[0,2]
当B的下标=3的时候，它唯一的区间是[2,3]
那么，由于产生了区间的概念，我们也随之创建两个指针，分别是head和tail，head指向的某区间开始位置的前一个位置；tail指向的是某区间结束为止的后一个位置。那么计算公式最终就是：(某元素下标位置 - head) * (tail - 某元素下标位置)。
我们得出了计算公式之后，就可以针对给出的字符串s中的每个字符进行遍历，在哈希表中记录一下每个元素的所在位置，key=字符，value=该字符出现的位置集合。具体实现，请参照：1> 采用哈希表方式实现。如果需要提升执行效率，我们也可以采用数组来记录每个元素的所在位置，26个字母对应数组的坐标，然后一个数组是用来针对某个元素出现多次进行统计计算的，另一个数组是用来针对只出现1次或者出现N次的最后1次这两个情况的字符进行计算的，具体实现，请参照：2> 采用数组方式实现。
解题思路我们就说完了。下面我们以s=“LEETCODE”为例，看一下具体的计算过程。由于下图中的计算细节已经在图中写出来了，所以这里的文字部分就不去赘述了。具体的计算过程，请参见下图：
四、代码实现
4.1> 采用哈希表方式实现
class Solution {
public int uniqueLetterString(String s) {
Map<Character, List<Integer>> map = new HashMap();
char[] sc = s.toCharArray();
for (int i = 0; i < sc.length; i++) {
if (!map.containsKey(sc[i])) map.put(sc[i], new ArrayList());
map.get(sc[i]).add(i);
}
int result = 0;
for(Map.Entry<Character, List<Integer>> entry : map.entrySet()) {
int head = -1, tail = -1;
List<Integer> item = entry.getValue();
for (int i = 0; i < item.size(); i++) {
tail = (i < item.size() - 1) ? item.get(i + 1) : sc.length;
result += (item.get(i) - head) * (tail - item.get(i));
head = item.get(i);
}
}
return result;
}
}
4.2> 采用数组方式实现
class Solution {
public int uniqueLetterString(String s) {
int ans = 0;
int[] tmp0 = new int[26]; //存储某一个字符前一个字符所在位置
int[] tmp1 = new int[26]; //存储某个字符当前所处位置
Arrays.fill(tmp0, -1);
Arrays.fill(tmp1, -1);
char[] chars = s.toCharArray();
for (int i = 0; i < chars.length; i++) {
char now = chars[i];
int index = now - 'A';
if (tmp1[index] > -1) {
ans += (i - tmp1[index]) * (tmp1[index] - tmp0[index]);
}
tmp0[index] = tmp1[index];
tmp1[index] = i;
}
for (int i = 0; i < 26; i++) {
if (tmp1[i] > -1) {
ans += (tmp1[i] - tmp0[i]) * (s.length() - tmp1[i]);
}
}
return ans;
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
