小红的子串权值和

[编程题]小红的子串权值和

热度指数：420 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小红定义一个字符串的权值为：极长“连续段”的数量。所谓极长“连续段”，指尽可能长的一段字符全部相同的连续子串。例如，"1100111" 共有 3 个连续段："11"、"00" 和 "111"，所以权值为 3。

现在小红拿到了一个 01 串，小红希望你帮她求出所有子串的权值之和。

提示：总共有 $C_{n+1}^2$ 个子串。

输入描述:

第一行输入一个正整数  ，代表字符串的长度。
第二行输入一个长度为  ，且仅由 '0' 和 '1' 两种字符组成的字符串。

输出描述:

一个正整数，代表所有子串的权值之和。

示例1

输入

4
1101

输出

说明

4个长度为1的子串的权值均为1。
长度为2的子串中，"11"的权值为1，"10"和"01"的权值均为2。
长度为3的子串中，"110"的权值为2，"101"的权值为3。
长度为4的子串"1101"的权值为3。
总权值为1*4+1+2+2+2+3+3=17。

算法知识视频讲解

Ahin

子串的权值之和考虑每个元素对子串权值的贡献
1.若si!=si-1 所有包含 s[i]的子串的权值都会 +1（因为新增了一个段）
这样的子串共有 (i + 1) * (n - i)个：
起始位置：可以是 0到 i（共 i + 1种选择）。
结束位置：可以是 i到 n - 1（共 n - i种选择）。
2.若si==si-1 则只对以该字符为起始点的子串有贡献，这样的子串共有 n - i个（结束位置从 i到 n - 1）
包含前面字符的子串，其权值已经由前面首个与前一字符不同的字符贡献了

编辑于 2025-09-16 17:03:14 回复(0)