遇到一个2n合体问题，求解答
有一个只包含小写字母n和t的字符串 s(1<=|s|<=1000000)，其中如果有两个n相邻，那么它们可以合并成一个m，现在需要你去求这个字符串中，含有多少个 'mtm' 这样的子序列。输入一行字符串 s；输出这个字符串中所包含的 mtm 子序列的个数。
展开
收起
1
条回答
写回答
写回答
-
对于每一个 t 进行单独考虑，计算这个 t 的左侧和右侧分别可以合成出多少种不同的 m，这两个数的乘积就是对于这个 t 来说的 mtm 子序列的个数。因为只有相邻的 n 才可以合成 m，所以 t 将原来的字符串分成了一系列 n 的串。例如：nnntnnnntnntnnn 被分成了 nnn nnnn nn nnn没有段包含的 m 个数分别为 2312对 于 每 个 t 来 说 的 mtm 子 序 列 就 分 别 是 2*（3+1+2） 、（2+3）*（1+2）、（2+3+1）*2；所以结果为 12+15+12=39 因此输入："nnntnnn" 输出：4
2021-12-23 18:55:43赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
