七 4261. 孤独的照片 (贡献法)

4261. 孤独的照片 (贡献法)

思路：从左向右统计与当前奶牛左侧连续不同品种的数量left，从右向左统计与当前奶牛右侧连续不同品种的数量right，最终结果就是每头奶牛right+left+left+right。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        String cows = sc.nextLine();
        long[] left = new long[n];
        long[] right = new long[n];
        for (int i = 0, sh = 0, sg = 0; i < n; i++) {
            if (cows.charAt(i) == 'G') {
                left[i] = sh;
                sg++;
                sh = 0;
            }
            else {
                left[i] = sg;
                sh++;
                sg = 0;
            }
        }
        for (int i = n - 1, sh = 0, sg = 0; i >= 0; i--) {
            if (cows.charAt(i) == 'G') {
                right[i] = sh;
                sg++;
                sh = 0;
            }
            else {
                right[i] = sg;
                sh++;
                sg = 0;
            }
        }
        long res = 0;
        for (int i = 0; i < n; i++) {
            res += (long) (left[i] * right[i] + Math.max(0, left[i] - 1) + Math.max(0, right[i] - 1));
        }
        System.out.println(res);
    }
}