题解 | 小红的子串权值和

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // // 注意 hasNext 和 hasNextLine 的区别
        // while (in.hasNextInt()) { // 注意 while 处理多个 case
        //     int a = in.nextInt();
        //     int b = in.nextInt();
        //     System.out.println(a + b);
        // }


        
        //先把数据读取进来
        int n = in.nextInt();
        in.nextLine();
        String s = in.nextLine();

        //使用动态规划来解决，关键是定义好dp数组
        //思路，定义dp[i]为以s[i]为结尾的子串的权值
        //递推公式为：dp[i] = 1（单独一个字符作为子串）+dp[i-1]（和前面的字符串连成一个字符串）（注意这种子串的数量为i） +i（如果s[i]和s[i-1]不同，则每个非单一字符子串的权值需要加一）/0（如果s[i]和s[i-1]相同）
        //
        long[] dp = new long[n];

        dp[0] = 1;
        long ans = 1;
        for(int i=1;i<n;i++){
            if(s.charAt(i)==s.charAt(i-1)){
                dp[i] = 1+dp[i-1];
            }else{
                dp[i] = 1+dp[i-1]+i;
            }
            ans = ans+dp[i];
        }

        System.out.println(ans);

    }
}