思路: 数学优化 + 哈希表

暴力思路：对于一个位置i，我们考虑往前找所有s[i] == s[j] 的位置j。那么[j+1,i-1]这一段的任意一个字符都可以被选择，也就是j对i的答案贡献就是j - i - 1。也就是找到所有的j，去求和。

那么位置i的答案是:

发现第一个求和式的内容(i - 1) 与 j无关:

答案就是 prefix[i] = prefix[i - 1] + ans_i

优化

根据上述式子我们发现

左边的求和式就是: [1 , i - 1] 内 与s[i] 相同的 数 的 个数

右边的求和式就是：[1 , i - 1] 内 与s[i] 相同的 数 的 下标和

那么我们在代码中使用哈希表mp[i] 维护 当前为止i出现的次数 以及 sm[i] 维护 当前i这个字符出现的下标和。

维护方法：每读到一个字符s[i]， mp[s[i]] += 1 , sm[s[i]] += i

复杂度：O(n) , 哈希的更新是O(1)的

Python代码

n = int(input())
s = input()

mp = {}
sm = {}
dp = [0] * (n + 1)
for i in range(1 , n + 1):
    cnt = mp.get(s[i - 1] , 0) 
    res = 0
    if cnt != 0:
        res = (i - 1) * cnt - sm.get(s[i - 1] , 0)
    dp[i] = dp[i - 1] + res
    mp[s[i - 1]] = cnt + 1
    sm[s[i - 1]] = sm.get(s[i - 1] , 0) + i

print(*dp[1:])

C++代码

#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;

    unordered_map<char, int> mp;  // 记录字符出现次数
    unordered_map<char, long long> sm;  // 记录字符位置前缀和
    vector<long long> dp(n + 1, 0);  // 记录答案

    for (int i = 1; i <= n; i++) {
        char c = s[i - 1];
        int cnt = mp[c];  // 统计 s[i] 出现的次数
        long long res = 0;

        if (cnt != 0) {
            res = (i - 1) * cnt - sm[c];  // 计算所有 j 对 i 的贡献
        }

        dp[i] = dp[i - 1] + res;  // 累加贡献

        // 更新 mp 和 sm
        mp[c] = cnt + 1;
        sm[c] += i;
    }

    for (int i = 1; i <= n; i++) {
        cout << dp[i] << " ";
    }
    cout << endl;

    return 0;
}

Java代码

import java.util.*;

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

        Map<Character, Integer> mp = new HashMap<>();  // 记录字符出现次数
        Map<Character, Long> sm = new HashMap<>();  // 记录字符位置前缀和
        long[] dp = new long[n + 1];  // 记录答案

        for (int i = 1; i <= n; i++) {
            char c = s.charAt(i - 1);
            int cnt = mp.getOrDefault(c, 0);  // 统计 s[i] 出现的次数
            long res = 0;

            if (cnt != 0) {
                res = (long) (i - 1) * cnt - sm.getOrDefault(c, 0L);  // 计算所有 j 对 i 的贡献
            }

            dp[i] = dp[i - 1] + res;  // 累加贡献

            // 更新 mp 和 sm
            mp.put(c, cnt + 1);
            sm.put(c, sm.getOrDefault(c, 0L) + i);
        }

        for (int i = 1; i <= n; i++) {
            System.out.print(dp[i] + " ");
        }
        System.out.println();

        sc.close();
    }
}

题目内容

小美定义一个字符串的权值为:其长度为3的回文子序列数量。例如，"$abca$"的权值为$2$，因为包含 两个回文子序列"$aba$"和"$aca$"。

现在给定一个仅包含小写字母的字符串，小美希望你输出该字符串每个前缀的权值。

输入描述

第一行输入一个正整数$n$，代表字符串长度。

第二行输入一个长度为$n$的、仅包含小写字母的字符 串。 $1≤n≤10^5$

输出描述

输出$n$个整数，分别代表长度为$1$到$n$每个前缀的权值。

样例1

输入

6
aaaaba

输出

0 0 1 4 4 14

说明

对于"$aaaaba$"，共有$10$个"$aaa$"子序列和$4$个"$aba$"子序列，因此权值是$14$。