子串分值

蓝桥杯练习题中子串分值-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;
 }
}

复杂度分析

提交详情

方法二：

思路

代码实现

复杂度分析

提交详情