题解 | #小红的子串权值和#

题目链接

题目描述

给定一个长度为 $n$ 的 01 字符串。一个字符串的“权值”被定义为其中极长连续相同字符段的数量。例如，字符串 "1100111" 的权值为 3，因为它由 "11"、"00" 和 "111" 三个连续段构成。

任务是计算该 01 字符串所有子串的权值之和。

解题思路

一个直接但效率不高的思路是枚举所有 $\frac{n \cdot (n + 1)}{2}$ 个子串，然后对每个子串计算其权值，最后将所有权值相加。这种方法的总时间复杂度为 $\mathcal{O}(n^3)$ ，对于典型的 $n$ 值（例如 $n \le 5000$ ）来说太慢了。

我们可以采用一种更高效的“贡献法”来解决此问题。我们将权值之和拆解为两部分来计算：

基础权值贡献：

任何一个非空子串都至少包含一个连续段，因此其权值至少为 1。字符串中总共有 $\frac{n \cdot (n + 1)}{2}$ 个子串。所以，所有子串的基础权值之和就是 $\frac{n \cdot (n + 1)}{2}$ 。
额外权值贡献：

一个子串的权值何时会大于 1 呢？当子串中存在相邻且不相同的字符时。例如，在 "10" 中，'1' 和 '0' 相邻且不同，使得权值从 1 增加到了 2。

我们可以遍历原字符串，考察每一对相邻且不同的字符 s[i-1] 和 s[i]（其中 s[i-1] != s[i]）。这个位置形成了一个“权值增加点”。任何一个跨越了这个“权值增加点”的子串，其权值都会因此而加 1。

那么，有多少个子串会跨越位置 $i-1$ 和 $i$ 呢？

一个跨越该位置的子串，其起始点必须在 $i-1$ 或之前，其结束点必须在 $i$ 或之后。
- 起始点可以选择的索引有 $0, 1, \dots, i-1$ ，共 $i$ 个。
- 结束点可以选择的索引有 $i, i+1, \dots, n-1$ ，共 $n - i$ 个。
因此，对于每一个满足 s[i-1] != s[i] 的位置 $i$ ，它都会为总权值和贡献 $i \cdot (n - i)$ 。

最终算法：

初始化总权值和 $total\_weight\_sum = \frac{n \cdot (n + 1)}{2}$ 。
遍历字符串的每个“权值增加点”，即从 $i = 1$ 到 $n-1$ 。
如果 s[i] != s[i-1]，则将 $i \cdot (n - i)$ 加到 $total\_weight\_sum$ 中。
遍历结束后， $total\_weight\_sum$ 即为最终答案。

这种方法的时间复杂度为 $\mathcal{O}(n)$ ，空间复杂度为 $\mathcal{O}(n)$ （用于存储输入字符串），效率很高。

代码

cpp
java
python

#include <iostream>
#include <string>
#include <vector>

using namespace std;

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

    int n;
    cin >> n;
    string s;
    cin >> s;

    long long total_weight_sum = (long long)n * (n + 1) / 2;

    for (int i = 1; i < n; ++i) {
        if (s[i] != s[i - 1]) {
            total_weight_sum += (long long)i * (n - i);
        }
    }

    cout << total_weight_sum << endl;

    return 0;
}

import java.util.Scanner;

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

        long totalWeightSum = (long)n * (n + 1) / 2;

        for (int i = 1; i < n; i++) {
            if (s.charAt(i) != s.charAt(i - 1)) {
                totalWeightSum += (long)i * (n - i);
            }
        }

        System.out.println(totalWeightSum);
    }
}

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

total_weight_sum = n * (n + 1) // 2

for i in range(1, n):
    if s[i] != s[i - 1]:
        total_weight_sum += i * (n - i)

print(total_weight_sum)

算法及复杂度

算法：数学 / 贡献法
时间复杂度： $\mathcal{O}(n)$ ，其中 $n$ 是字符串的长度。我们只需要对字符串进行一次线性扫描。
空间复杂度： $\mathcal{O}(n)$ ，主要用于存储输入的字符串。