11294805 小红的偏移值

题目链接: https://www.nowcoder.com/practice/adfc6ec3f23747a38c0029bec76127cd

题意

给定一个只含小写字母的字符串，定义一个字符串的「偏移值」为其中不同字母的数量。求所有非空子串的偏移值之和。

思路

贡献法。不直接枚举每个子串计算不同字母数（O(n^3) 或 O(n^2)），而是对每个字符位置 i，计算 s[i] 在多少个子串中「首次出现」，即作为该字符在子串中的最左出现位置。

设 prev[i] 为 s[i] 在位置 i 之前最近一次出现同一字母的位置（不存在则为 -1）。

那么 s[i] 作为其字符的第一次出现（即贡献 +1 到偏移值）的子串 [l, r] 需满足：

prev[i] < l <= i（左端点必须在上次同字母出现之后，才保证 s[i] 是该字符在子串内的首次出现）
i <= r <= n-1（右端点可以从 i 一直延伸到末尾）

满足条件的子串数量为：

$ $\text{count}(i) = (i - \text{prev}[i]) \times (n - i)$ $

答案即为所有位置贡献之和：

$ $\text{ans} = \sum_{i=0}^{n-1} (i - \text{prev}[i]) \times (n - i)$ $

时间复杂度 O(n)，空间复杂度 O(26)。

验证

以 "abcd" 为例（n=4，每个字母均无重复，prev 全为 -1）：

i	字符	prev	贡献 (i-prev)*(n-i)
0	a	-1	(0-(-1))*(4-0) = 4
1	b	-1	(1-(-1))*(4-1) = 6
2	c	-1	(2-(-1))*(4-2) = 6
3	d	-1	(3-(-1))*(4-3) = 4

总和 = 20，与示例一致。

代码

C++

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s;
    cin >> s;
    int n = s.size();

    vector<int> last(26, -1);
    long long ans = 0;

    for (int i = 0; i < n; i++) {
        int c = s[i] - 'a';
        int prev = last[c];
        ans += (long long)(i - prev) * (n - i);
        last[c] = i;
    }

    cout << ans << endl;
    return 0;
}

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine().trim();
        int n = s.length();

        int[] last = new int[26];
        Arrays.fill(last, -1);
        long ans = 0;

        for (int i = 0; i < n; i++) {
            int c = s.charAt(i) - 'a';
            int prev = last[c];
            ans += (long)(i - prev) * (n - i);
            last[c] = i;
        }

        System.out.println(ans);
    }
}

复杂度

时间复杂度：O(n)
空间复杂度：O(26) = O(1)