题目描述

乘法原理：可能性相乘
贡献法：看一下，该字串是如何对结果产生影响的

一共三种情况：
1.左边有连续1、2…L个与自己不相同的字母，右边有连续1、2…R个与自己不相同的字母
，数量L*R

2.左边有连续2、3…L个与自己不相同的字母，右边都是和自己相同的，数量就为L-1

3.右边有连续2、4…L个与自己不相同的字母，左边都是和自己相同的，数量就为R-1

样例

import java.util.Scanner;

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

        //存储当前位置左边有多少个连续的位置的字母与自己不一样 因为是子串一定是连续的，子序列是不连续的
        int[] l = new int[n];
        //存储当前位置右边有多少个连续的位置的字母与自己不一样 因为是子串一定是连续的，子序列是不连续的
        int[] r = new int[n];

        //统计左半区间
        for (int i = 0 ,h = 0 , g = 0; i < n; i++) {
            if (str.charAt(i) == 'G') {
                l[i] = h;//存储当前位置左边有多少个连续的h
                h = 0;//h置为0，说明连续的h中断了,因为当前位置为g
                g++;
            } else {
                l[i] = g;//存储当前位置左边有多少个连续的g
                g = 0;//g置为0，说明连续的g中断了,因为当前位置为h
                h++;
            }
        }

        //统计右半区间
        for (int i = n - 1,h = 0 , g = 0; i >= 0; i--) {
            if (str.charAt(i) == 'G') {
                r[i] = h;//存储当前位置右边有多少个连续的h
                h = 0;//h置为0，说明连续的h中断了,因为当前位置为g
                g++;
            } else {
                r[i] = g;//存储当前位置右边有多少个连续的g
                g = 0;//g置为0，说明连续的g中断了,因为当前位置为h
                h++;
            }
        }

        long res = 0;
        for (int i = 0; i < n; i++) {
            //l[i]和r[i]有可能等于0，要和0比较一下
            res += (long) l[i] * r[i] + Math.max(l[i] - 1, 0) + Math.max(r[i] - 1, 0);
        }

        System.out.println(res);
    }
}