题意整理。

• 给定长度为n的字符串。
• 求"abb"型子序列的个数。

方法一（后缀和数组）

1.解题思路

• 首先进行预处理，得到对应的后缀和数组。
• suffix[i+1][j]表示str中第i个字母之后的对应字母出现次数，所以可以在$O(1)O(1)$时间内，获得当前字母之后的对应字母出现次数。然后计算对应生成的"abb"型子序列的个数。

举例说明：对于字符串"abcbcc"，若当前字母为a，则可生成一个"abb"，三个"acc"，出现在a之后的b有2个，出现在a之后的c有3个，假设这个出现次数记为t，则对应新增的"abb"型子序列的个数为$t\ast (t-1)\mathrm{/}2t*(t-1)/2$，即为对应字母的组合数。

图解展示：

2.代码实现

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        //输入字符串
        String str=sc.next();
        
        //后缀和数组，suffix[i+1][j]表示str中第i个字母之后的对应字母出现次数
        int[][] suffix=new int[n+1][26];
        for(int i=n-1;i>=0;i--){
            char c=str.charAt(i);
            for(int j=0;j<26;j++){
                suffix[i][j]=suffix[i+1][j];
            }
            suffix[i][c-'a']++;
        }
        
        //记录所有"abb"型子序列的个数
        long res=0;
        
        for(int i=0;i<n;i++){
            char c=str.charAt(i);
            for(int j=0;j<26;j++){
                //加上当前字母为前缀，所组成的"abb"型子序列的个数
                if(j!=c-'a'&&suffix[i][j]>=2){
                    res+=suffix[i+1][j]*(suffix[i+1][j]-1)/2;
                }
            }
        }
        
       
        System.out.println(res);
    }
}

3.复杂度分析

• 时间复杂度：两层循环，最多执行$26\ast n26*n$次，所以时间复杂度为$O(n)O(n)$。
• 空间复杂度：需要额外大小为$26\ast (n+1)26*(n+1)$的后缀和数组，所以空间复杂度为$O(n)O(n)$。