题解 | #abb#

初读题目没有太多思路，只觉得暴力穷举时间复杂度太高，应该过不了。看一了下排行榜里的代码，没有太多注释，看不太明白。理解了一会，按照我自己的理解添加了一些注释。

主要是理解 dp 数组的含义，sum数组表示的是 26 个字母出现的次数，dp 数组存储的是 26个字母能形成ab形式的个数。遍历的时候，idx 为 当前字母在 26字母表中的位置，abb个数的总计数器需要 + dp[idx]，表示前面可以形成 ab 形式的子序列加上当前的这个字母，就能形成abb的形式。dp 的更新则是在计数器更新之后，dp 只需要 + 前面的字符串中不为 当前字母的数量（即第一个字符 与 第二个字符不一样的个数，即为 当前索引 i - 当前字母出现的次数 sum[idx]）。表达不太清晰的位置望理解。

import java.util.Scanner;
import java.io.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String str = br.readLine();
        long[] sum = new long[26];  // sum[i] 表示 字母表中第 i 个字母，在 str 中 出现的次数
        long[] dp = new long[26];  // dp[i] 表示 字母表中第 i 个字母，在 str 中 可以组成 ab 的个数，当再次遇到 第 i 个字母的时候，能组成abb的个数 + dp[i] 即可
        long result = 0;
        
        // 遍历 str，取出每一个 char，计算在字母表中的 idx （是字母表中的第几个）
        for (int i = 0; i < n; i++) {
            int index = str.charAt(i) - 'a';
            // 计数器 加上 dp[idx]（dp[idx] 表示前面的 子序列中 当前字母 char 能形成 ab 形式的个数，前面能形成 ab 的序列 + 当前的 char 即可形成 abb 的形式）
            result += dp[index];
            // 更新 dp：当前 在字符串中的 索引 - 当前字符 char 出现的次数，即 前面有多少个不为 char 的字符
            dp[index] += i - sum[index];
            // 计数 char 出现的次数
            sum[index]++;
        }
        System.out.println(result);
    }
}