题目大意：
独特字符串
如果一个字符在字符串 S 中有且仅有出现一次，那么我们称其为独特字符。
例如，在字符串 S = “LETTER” 中，”L” 和 “R” 可以被称为独特字符。
我们再定义 UNIQ(S) 作为字符串 S 中独特字符的个数。
那么，在 S = “LETTER” 中， UNIQ(“LETTER”) = 2。
对于给定字符串 S，计算其所有非空子串的独特字符的个数（即 UNIQ(substring)）之和。
如果在 S 的不同位置上出现两个甚至多个相同的子串，那么我们认为这些子串是不同的。
考虑到答案可能会非常大，规定返回格式为：结果 mod 10 ^ 9 + 7。
示例 1:
输入: "ABC"
输出: 10
解释: 所有可能的子串为："A","B","C","AB","BC" 和 "ABC"。
其中，每一个子串都由独特字符构成。
所以其长度总和为：1 + 1 + 1 + 2 + 2 + 3 = 10示例 2:
输入: "ABA"
输出: 8
解释: 除了子串 UNIQ('ABA') = 1，其余与示例1相同。 说明: 0 <= S.length <= 10000。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=828
解题思路分析：
这道题java语言使用暴力解是可以通过TC的，但效率不高，大概需要1300多毫秒。解法二会给出相关的解题思路，仅供参考。
解法一：
在字符串的任意子串中，对结果起到实际作用的是只出现过一次的字母，因此对于任意一个字母，我们只要找到了一个区间，保证其只出现一次的话，那么它的输出应该都在这个范围之内，举个例子，比如下面这个字符串：
ABFCDEFXYZF
对于第一个红色的F，在区间ABFCDE中，只出现了1次，这时，F左边有2个字母，右边有3个字母，因此F的总输出应该是 2 + 3 + 2*3 + 1。其中2代表了以F结尾的长度大于1的子串个数，3代表以F开头的长度大于1的子串个数，2*3则是F在中间的子串个数，1是F自身。
同理，对于第二个蓝色F，它的总输出应该是： 3 + 3 + 3*3 + 1。
最后一个粉色F的输出为：3 + 0 + 3*0 + 1
有了上面的思路，我们可以这样来解题，首先循环一遍字符串，统计出每种字母出现的位置，然后，遍历每种字母的位置，当前位置与同字母前一位置和同字母后一位置之间的部分就是当前字母唯一出现的区间，遍历所有字母之后即可得出答案。
实现代码：
public int uniqueLetterString(String S) {
// 统计每种字母出现的位置
List<Integer>[] posiitons = new List[26];
for(int i=0;i<S.length();i++){
int c = S.charAt(i)-'A';
List<Integer> list = posiitons[c];
if(list==null) list=new ArrayList<>();
list.add(i);
posiitons[c]=list;
}
int res=0; // 返回结果
// 遍历每种大写字母
for(List<Integer> list : posiitons){
// 如果该字母没在字符串中出现过，跳过
if(list==null) continue;
// 循环所有出现的位置
for(int i=0;i<list.size();i++){
// 当前位置
int currentIndex=list.get(i);
// 同字母前一出现位置，如果左方没有该字母，前位置为字符串首位
int leftIndex= i==0 ? 0 :list.get(i-1)+1;
// 同字母后一出现位置，如果右方没有该字母，后位置为字符串末尾
int rightIndex=i==list.size()-1?S.length()-1:list.get(i+1)-1;
// 左区间长度
int l=currentIndex-leftIndex;
// 右区间长度
int r=rightIndex-currentIndex;
// 计算输出
int count = l+r+l*r+1;
res+=(count%1000000007);
}
}
return res;
}本解法执行时间为13ms。
Runtime: 13 ms, faster than 36.07% of Java online submissions for Unique Letter String.
Memory Usage: 37.1 MB, less than 66.67% of Java online submissions for Unique Letter String.
解法二，暴力解
暴力解思路更加清晰，既然求所有子串，那么我们就遍历出所有子串即可，两层循环，第一层为子串开头位置，第二层为子串长度。由于子串长度是从1开始，因此，此时的解sum是1。利用一个count数组，记录下当前字符出现过的次数，继续循环，如果当前字母出现次数为0，说明之前没有出现过，这时的独特字符加一，因此sum较前一次循环时加一。如果当前字符出现过次数为1，说明之前他是独特字符，因当前位也是该字符，表明他不再是独特字符，此时sum应该减一。如果该字母出现过2次以上，说明他之前就已经不是独特字符，此时sum不变。每一次循环都将sum累加至返回结果，循环结束后，便可统计出全部答案。
另外暴力解可以做出一些剪枝优化，当所有26个字母都不再是独特字符后，当前子串无需再继续循环下去（之后的结果都是0），返回上层循环，改变子串开头位置继续即可。
实现代码（不加注释了）：
public int uniqueLetterString(String S) {
int res=0;
for(int i=0;i<S.length();i++){
int[] count=new int[26];
int unique=26;
int sum=0;
for(int j=i;j<S.length();j++){
if(unique==0) break;
int c = S.charAt(j)-'A';
if(count[c]==0){
sum++;
}else if(count[c]==1){
sum--;
unique--;
}
res+=(sum % 1000000007);
count[c]++;
}
}
return res;
}本解法执行时间为1283ms。
Runtime: 1283 ms, faster than 5.25% of Java online submissions for Unique Letter String.
Memory Usage: 36.7 MB, less than 66.67% of Java online submissions for Unique Letter String.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-828-unique-letter-string-解题思路分析/