第十一届蓝桥杯A组省赛试题 H: 子串分值（Java）

试题 H: 子串分值

时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分

【问题描述】

对于一个字符串 S，我们定义 S 的分值 f(S) 为 S 中恰好出现一次的字符个数。例如 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。

【思路】

①暴力会超时

②只有当字母出现的次数为1才有贡献度，因此我们只需要计算出每个位置的贡献度累加求和即为答案。例如ababc，如果我们求第二个位置b的贡献度，则以b为中心，向两边扩散，找到只有一个b时的最长子串，向左步长为left=1，即ababc，向右步长为right=1，即ababc,所以我们找到的子串为aba，它一共有ab,aba,b,ba 4种组合，从左到b做起点，从b到右做终点，即贡献度=(left+1)*(right+1)。

【Java代码】

import java.util.Scanner;
public class Main {
  public static void main(String[] args) {
  Scanner scanner = new Scanner(System.in);
  String inputString = scanner.next();
  long res = 0;
  for (int i = 0; i < inputString.length(); i++) {
    int left = 0, right = 0;
    //统计左右步长
    while(i-left > 0 && inputString.charAt(i-left-1) != inputString.charAt(i)) left++;
    while (i+right+1 < inputString.length() && inputString.charAt(i+right+1) != inputString.charAt(i)) right++;
    res += (1+left)*(1+right);
  }
  System.out.println(res);
  }
}