蓝桥杯|历届真题:子串分值和

1.题目

【问题描述】
对于一个字符串$S$，我们定义S的分值$f(S)$为$S$中恰好出现一次的字符个数。例如$f(aba)=1，f(abc)=3，f(aaa) = 0$。
现在给定一个字符串$S[0..n-1]$（长度为n），请你计算对于所有S的非空子串$S[i..j]（0 \leq i \leq j \lt 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 \leq n \leq 10$；
对于40%的评测用例， $1 \leq n \leq 100$；
对于50%的评测用例， $1 \leq n \leq 1000$；
对于60%的评测用例， $1 \leq n \leq 10000$；
对于所有评测用例， $1 \leq n \leq 100000$；

2. 题解

2.1 思路分析

思路1：暴力求解(50分)
    首先需要写一个计算子串得分的函数
        1.统计各个字符出现的次数
        2.得到只出现一次的字符数
    然后遍历所有的子串并对其得分进行求和

思路2：动态规划(50分)
    考虑子串之间的关系,即新增一个字符对子串得分的影响,从避免重复统计字符出现次数导致耗时

思路3:考虑每个位置的字符只出现一次的子串总数(100分)
用 pre[i] 记录第 i 位置上的字母上一次出现的位置，用 next[i] 记录第 i 位置上的字母下一次出现的位置；
那么往左最多能延伸到 pre[i] + 1，其到第 i 个字母一共有 i - pre[i] 个字母；
同理往右最多能延伸到 next[i] - 1，其到第 i 个字母一共有 next[i] - i 个字母；
二者相乘，就是该 i 位置上的字符只出现一次的子串总数
具体可以结合上述输入输出例子思考。

2.2 代码实现

• 思路1：暴力求解

import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);
    public static int getScore(String str){
        int score = 0;
        char[] strChars = str.toCharArray();
        int[] charCounter = new int[26];
        for (int i = 0; i < 26; i++)charCounter[i]=0;

        for (int i = 0; i < strChars.length; i++) {
          charCounter[(int)(strChars[i]-'a')]++;
        }

        for (int i = 0; i <26 ; i++) {
            if(charCounter[i]==1)score++;
        }
        return score;
    }
    
    public static void main(String[] args) {
        String str = scanner.next();
        char[] strChars = str.toCharArray();
        int scoreSum = 0;
        for (int i = 0; i < strChars.length; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = i; j < strChars.length; j++) {
                sb.append(strChars[j]);
                scoreSum+=getScore(sb.toString());
            }
        }
        System.out.println(scoreSum);
    }
}

// 简化子串得分求解
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);
    
    public static void main(String[] args) {
        String str = scanner.next();
        int len = str.length();
        char[] strChars = str.toCharArray();

        int scoreSum = 0;

        for (int i = 0; i < strChars.length; i++) {
            Set<Character> set1 = new HashSet<>(); //统计所有字符串
            Set<Character> set2 = new HashSet<>();//统计不止出现一次的字符串
            for (int j = i; j < strChars.length; j++) {
                if(set1.contains(strChars[j])){
                    set2.add(strChars[j]);
                }
                set1.add(strChars[j]);
                scoreSum+= set1.size()-set2.size();
            }
        }
        System.out.println(scoreSum);
    }
}

• 思路2：动态规划

// 40分 会爆内存
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        String str = scanner.next();
        char[] strChars = str.toCharArray();
        int[][] dp = new int[str.length()][str.length()];
        int scoreSum = 0;
        for (int i = 0; i < str.length(); i++) {
            for (int j = 0; j < str.length();j++) {
                if(j<i){
                    dp[i][j] = 0;
                }else if(j==i){
                    dp[i][j] = 1;
                }else {
                    int startIndex = str.substring(i,j).indexOf(strChars[j]);
                    if(startIndex!=-1){//旧的子包含待加入字符
                        int endIndex = str.substring(i,j).lastIndexOf(strChars[j]);
                        if(startIndex==endIndex){//旧的子串只包含1个待加入字符
                            dp[i][j]=dp[i][j-1]-1;
                        }else {//旧的子串包含多个个待加入字符，之前已进行了-1操作，无需再减
                            dp[i][j]=dp[i][j-1];
                        }
                    }else {//旧的子不包含待加入字符
                        dp[i][j]=dp[i][j-1]+1;
                    }
                }
                scoreSum += dp[i][j];
            }
        }

        System.out.println(scoreSum);
    }
}

// dp优化 避免爆内存 还是50分
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);
    public static void main(String[] args) {
        String str = scanner.next();
        int len = str.length();
        char[] strChars = str.toCharArray();
        int lastDpstate = 0;
        int scoreSum = 0;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len;j++) {
                if(j<i){
                    lastDpstate=0;
                }else if(j==i){
                    lastDpstate = 1;
                }else {
                    int startIndex = str.substring(i,j).indexOf(strChars[j]);
                    if(startIndex!=-1){//旧的子串包含待加入字符
                        int endIndex = str.substring(i,j).lastIndexOf(strChars[j]);
                        if(startIndex==endIndex){//旧的子串只包含1个待加入字符
                            lastDpstate=lastDpstate-1;
                        }
                    }else {
                        lastDpstate=lastDpstate+1;
                    }
                }
                scoreSum += lastDpstate;
            }
        }

        System.out.println(scoreSum);
    }
}

• 思路3：考虑每个位置的字符只出现一次的子串总数

// 60分
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        String str = scanner.next();
        char[] strChars = str.toCharArray();
        int scoreSum = 0;

        for (int i = 0; i < strChars.length; i++) {
            int nextIndex = str.substring(i+1).indexOf(strChars[i]); //下一个strChars[i]字符的位置
            nextIndex = nextIndex==-1? strChars.length : nextIndex+i+1;

            int preIndex = str.substring(0,i).lastIndexOf(strChars[i]);////前一个strChars[i]字符的位置

            scoreSum += (nextIndex-i)*(i-preIndex);
        }

        System.out.println(scoreSum);
    }
}

// 优化 100分
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        String str = scanner.next();
        char[] strChars = str.toCharArray();
        int len = strChars.length;
        int scoreSum = 0;

        int[] pre = new int[len];
        int[] next = new int[len];

        Arrays.fill(pre,-1);
        Arrays.fill(next,len);


        // 求解next[i]
        for (int i = 0; i < len; i++) {
            for (int j = i+1; j < len; j++) {
                if(strChars[i]==strChars[j]){
                    next[i]=j;
                    break;
                }
            }
        }

        // 求解pre[i]
        for (int i = 0; i < len; i++) {
            for (int j = i-1; j>=0; j--) {
                if(strChars[i]==strChars[j]){
                    pre[i]=j;
                    break;
                }
            }
        }
        
        // 计算得分和
        for (int i = 0; i < len; i++) {
            scoreSum += (next[i]-i)*(i-pre[i]);
        }

        System.out.println(scoreSum);
    }
}

2.3 提交结果

• 思路1：暴力求解

• 思路2：动态规划

• 思路3：考虑每个位置的字符只出现一次的子串总数

参考资料

1. http://lx.lanqiao.cn/problem.page?gpid=T2858
2. 蓝桥杯试题 历届试题 子串分值和