算法前缀和之abb

package com.zhang.reflection.面试.算法模版.前缀和;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
 * leafee 最近爱上了 abb 型语句，比如“叠词词”、“恶心心”
 * leafee 拿到了一个只含有小写字母的字符串，她想知道有多少个 "abb" 型的子序列？
 * 定义： abb 型字符串满足以下条件：  (子序列不要求连续，子串要求连续)
 *
 * 字符串长度为 3 。
 * 字符串后两位相同。
 * 字符串前两位不同。
 */
public class abb {
    /**
     * 可以说是前序和感觉
     * 先计算当前往前有多少个不同组合，直到遇到下一个相同字符再累加进去
     * abcbcc
     * 就以c来说
     * 第一次c前面有ab组合两种，dp['c'-'a'] = 0;
     * 第二个c前面有abcb有三种abb三种组合 dp['c'-'a'] = 2
     * 第三个c的时候可以和第一个组合，有两种，第二组合有三种，dp['c'-'a'] = 5
     * 第一次 0种符合的组合，第二次有2种符合的组合，第三次有5种符合的组合
     * 关键要先计数，下次遇到相同的字符再累加
     * @param
     * @return
     * @author louss
     * @date 2022/4/10 17:32
     */
    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];
        long[] dp = new long[26];
        long result = 0;
        for(int i=0;i<n;i++){
            int index = str.charAt(i)-'a';
            result += dp[index];
            dp[index] += i - sum[index];
            sum[index]++;
        }
        System.out.println(result);
    }
}