题目
对于一个字符串 ,我们定义 的分值 为 中出现的不同的字符个数。例如 。
现在给定一个字符串 (长度为 ),请你计算对于所有 的非空子串 , 的和是多少。
输入描述
输入一行包含一个由小写字母组成的字符串 。
其中,。
输出描述
输出一个整数表示答案。
输入输出样例
示例 1
输入
ababc
输出
28
运行限制
- 最大运行时间:1s
- 最大运行内存: 128M
解题
方法一:递推
思路
代码
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String s = in.readLine();
int n = s.length();
char[] chs = ('0' + s).toCharArray();
int[] prevs = new int[26];
long ans = 0L;
for (int i = 1; i <= n; ++i) {
int curr = chs[i] - 'a';
ans += (long) (i - prevs[curr]) * (n - i + 1);
prevs[curr] = i;
}
System.out.println(ans);
}
}
评论区