abb

[编程题]abb

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

leafee 最近爱上了 abb 型语句，比如“叠词词”、“恶心心”

leafee 拿到了一个只含有小写字母的字符串，她想知道有多少个 "abb" 型的子序列？
定义： abb 型字符串满足以下条件：

字符串长度为 3 。
字符串后两位相同。
字符串前两位不同。

输入描述:

第一行一个正整数 
第二行一个长度为  的字符串（只包含小写字母）

输出描述:

"abb" 型的子序列个数。

示例1

输入

6
abcbcc

输出

说明

共有1个abb，3个acc，4个bcc

示例2

输入

4
abbb

输出

算法知识视频讲解

其实是牛哥

发表于 2021-10-19 15:17:53

abb 难度：3星提示 1：对于每个字母 ch，找到后面和 ch 不等的两个相等字母的个数 cnt 即可，贡献为 Ccnt2=cnt∗(cnt−1)/2C_{cnt}^2=cnt*(cnt-1)/2Ccnt2=cnt∗(cnt−1)/2 提示 2：快速得出每个 cnt 的方式：开一个后缀和数组展开全文

xqxls

发表于 2021-10-26 15:01:22

题意整理。给定长度为n的字符串。求"abb"型子序列的个数。方法一（后缀和数组） 1.解题思路首先进行预处理，得到对应的后缀和数组。 suffix[i+1][j]表示str中第i个字母之后的对应字母出现次数，所以可以在O(1)O(1)O(1)时间内，获得当前字母之后的对应字母出现次数。展开全文

冷吃掉的静

发表于 2022-04-18 16:01:52

简单易懂思路：用abb中第一个出现的b来考虑，一个字符作为第一b能产生的abb字符，等于它后面相同的字符数量（意味着还能凑成多少个bb）乘以它前面与它不相同的字符数量（可以被当作a的）。于是先记录每一个字符总出现的次数。然后再遍历字符串记录每个字符已经出现的次数和后面还没出现的次数。 #includ 展开全文

wangpucong

发表于 2021-11-27 16:11:26

cnt[i] 表示在索引为0~i-1 之间小写字母出现的次数，i-cnt[i]表示除了这个字符以外其他字符的数量，这样我们就可以统计出像 ab这样的字符串有多少个使用dp[i]记录 0~i-1 之间以字符s[i]结尾的字符串有多少 #include<stdio.h> int ma 展开全文

bibibibi

发表于 2021-11-02 23:39:14

描述给一个长度为nnn的字符串，问有多少个形式为abb的子序列思路一个比较常见的动态规划题目，设dp[i][j]dp[i][j]dp[i][j]表示区间[1,i][1,i][1,i]中以字母jjj为结尾，有多少个形式为ab的子序列，则对于字符串sss最终的答案为∑i∈[1,n]dp[i−1 展开全文

文和906

发表于 2021-10-28 11:46:21

开始时设想使用前缀和的方法，建立一个sum数组，其中sum.at(i)保存的是前i项中abb的个数。按顺序遍历字符串，使用一个二重循环，对每一个字符都统计其在之前出现的次数以及其他字符出现的位置，按照C(2,n)的组合数计算规则可以发现C(2,1), C(2,2), ..., C(2,n)组成的数列展开全文