蓝桥杯练习题中子串分值-java
题目
题目描述
对于一个字符串 SS,我们定义 SS 的分值 f(S)f(S) 为 SS 中恰好出现一次的字符个数。例如 f(“aba”) = 1,f(“abc”) = 3, f(“aaa”) = 0f(“aba“)=1,f(“abc“)=3,f(“aaa“)=0。
现在给定一个字符串 S_{0 \cdots n − 1}S0⋯n−1(长度为 nn,1 \leq n \leq 10^51≤n≤105),请你计算对于所有 SS 的非空子串 S_{i \cdots j}(0 ≤ i ≤ j < n)S**i⋯j(0≤i≤j<n),f(S_{i \cdots j})f(S**i⋯j) 的和是多少。
输入描述
输入一行包含一个由小写字母组成的字符串 SS。
输出描述
输出一个整数表示答案。
输入输出样例
示例
输入
ababc
输出
21
运行限制
- 最大运行时间:1s
- 最大运行内存: 256M
题解
方法一:
思路
遍历所有的子串,每个子串计算它的出现一次字符的个数,然后加上所有子串的个数即为总个数和
import java.util.Scanner;
//1:无需package
//2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
String str = scan.next();
int sum = 0;
int n = str.length();
for(int i = 0; i < n - 1; i++){
for(int j = i + 1; j <= n; j++){
System.err.println(str.substring(i, j));
sum += everyNum(str.substring(i, j));
}
}
// 这里sum+1 是因为substring是截取不到最后一个字符的,如字符串ab, 上述截取的子串为a , ab,但是并无最后一个字符b,所以要加1,因为最后一个字符也为1
System.out.println(sum+1);
scan.close();
}
public static int everyNum(String str){
int[] arr = new int[26];
for(int i = 0; i < str.length(); i++){
arr[str.charAt(i) - 'a']++;
}
int num = 0;
for(int i = 0; i < 26; i++){
if(arr[i] == 1){
num++;
}
}
return num;
}
}