题目描述

贡献法

样例

import java.util.Scanner;

/*
   使用贡献法：看看当前位置的字母对结果的影响
   每个为位置的结果：
   （该位置-该位置的字母在左边区间最后一次出现的位置）*（该位置的字母在右边区间最后一次出现的位置-该位置）

   对于边界情况：
   1.在左半区间，假如该字母第一次出现，想象0位置有一个该字母，我们发现(i - l[i]) * (r[i] - i)没有影响
   2.在右半区间，假如该字母在最末端出现，想象n+1位置有一个该字母，我们发现(i - l[i]) * (r[i] - i)有影响
   所以在处理完左半区间，我们先对p操作一下，再去处理右半区间，我们先把每个字母最后出现的位置都设为n+1，
   这样就便利了很多，非常巧妙的写法
*/


public class Main {

    static int N = 100010;
    //
    static int[] l = new int[N];
    //
    static int[] r = new int[N];
    //存储每个字母最后出现的位置
    static int[] p = new int[26];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.next();
        int n = str.length();

        for (int i = 1; i <= n; i++) {
            //把a-z映射到0到25
            int t = str.charAt(i - 1) - 'a';
            //存储当前位置的该字母在左边区间最后出现的位置
            l[i] = p[t];
            //存储当前位置的该字母最后出现的位置
            p[t] = i;
        }

        //处理某个字母第一次出现在最后面, 于是乎我们先把每个字母最后出现的位置都设为n+1,
        for (int i = 0; i < 26; i++) {
            p[i] = n + 1;
        }

        for (int i = n; i >= 1; i--) {
            //把a-z映射到0到25
            int t = str.charAt(i - 1) - 'a';
            //存储当前位置的该字母在右边区间最后出现的位置
            r[i] = p[t];
            //存储当前位置的该字母最后出现的位置
            p[t] = i;
        }

        long res = 0;
        for (int i = 1; i <= n; i++) {
            res += (long) (i - l[i]) * (r[i] - i);
        }

        System.out.println(res);
    }
}

1.在左半区间，假如该字母第一次出现，想象0位置有一个该字母，我们发现(i - l[i]) * (r[i] - i)没有影响

2.在右半区间，假如该字母在最末端出现，想象n+1位置有一个该字母，我们发现(i - l[i]) * (r[i] - i)有影响
所以在处理完左半区间，我们先对p操作一下，再去处理右半区间，我们先把每个字母最后出现的位置都设为n+1，这样就便利了很多，非常巧妙的写法