【资源限制】

        内存限制：256.0MB   C/C++时间限制：1.0s   Java时间限制：3.0s   Python时间限制：5.0s

【问题描述】

        对于一个字符串 SS，我们定义 SS 的分值 f(S)f(S) 为 SS 中恰好出现一次的字符个数。例如 f("aba") = 1，f("abc") = 3, f("aaa") = 0。

        现在给定一个字符串 S[0..n − 1]（长度为 n），请你计算对于所有 S 的非空子串 S[i..j](0 ≤ i ≤ j < n)，f(S[i..j])的和是多少。
【输入格式】

        输入一行包含一个由小写字母组成的字符串S。

【输出格式】

        输出一个整数表示答案。

【样例输入】

ababc

【样例输出】

21

【样例说明】

子串        f值

a                1

ab              2

aba            1

abab          0

ababc        1

b                1

ba              2

bab            1

babc          2

  a              1

  ab            2

  abc          3

    b            1

    bc          2

      c          1

【评测用例规模与约定】

        对于20%的评测用例，1 ≤n≤ 10；

        对于40%的评测用例，1≤n≤100；

        对于50%的评测用例，1≤n≤1000；

        对于60%的评测用例，1≤n ≤10000；

        对于所有评测用例，1≤n ≤100000。

【思路与分析】

        这道题初看没有什么思路，但多看几遍就看出来点东西了。可以使用Set集合的“不重复”特性来解题，这我就想到了先用暴力法试试，不出意料的超时了。只能OJ50%，而后也没有一些好的想法。

        于是，想到了参考题解来试着解题。题解的做法也是蛮简单的，一点就通了属于是。原理就是创建一个新的衡量标准，该标准只有在该字母出现且只出现一次的情况下进行+1，我们将它称为“贡献度”。

        比如说，从字母a的两边出发，分别计算左右两边要“走”多远才能遇到重复，此时停止遍历，并记录下左、右步数。

        贡献度 =(左步数+1) * (右步数+1)；

        以题中所给的ababc为例：我们从中间的那个a开始向左、向右遍历

       1.先向左，移动2个单位遇到重复，记录下left=2

        2.再向右，移动3个单位都没有遇到重复，而子串结束，记录下right=3

        贡献度 = 3 * 4

        贡献度 = 12

【代码：满分】

import java.util.Scanner;public class Main {static int r = 0;public static void main(String[] args) {Scanner sc = new Scanner(System.in);String str = sc.nextLine();char[] arr = str.toCharArray();for(int i = 0; i < arr.length; i++){int left = 0;int right = 0;for(int j = i - 1; j >= 0 && arr[j] != arr[i]; j--){left++;}for(int j = i + 1; j < arr.length && arr[j] != arr[i]; j++){right++;}r += (left + 1) * (right + 1);}System.out.println(r);}
}

【代码：OJ50%】

import java.util.Scanner;public class Main {static int r = 0;public static void main(String[] args) {Scanner sc = new Scanner(System.in);String str = sc.nextLine();for(int i = 0; i < str.length(); i++){for(int j = i; j < str.length(); j++){//左闭右开count(str.substring(i,j+1));}}System.out.println(r);}public static void count(String str){int[] arr = new int[26];for(int i = 0; i < str.length(); i++){char c = str.charAt(i);arr[c - 'a']++;}for(int i = 0; i < arr.length; i++){if(arr[i] == 1){r++;}}}
}