首页 > 试题广场 >

小红的子串权值和

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

小红定义一个字符串的权值为：极长“连续段”的数量。所谓极长“连续段”，指尽可能长的一段字符全部相同的连续子串。例如，"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。

算法知识视频讲解

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

前缀和组合数学字节跳动

来自：2024秋招-字节跳动...

难度：

0条回答 4收藏 118浏览

小红的子串权值和

扫一扫，把题目装进口袋