在线编程介绍
阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：https://developer.aliyun.com/coding
本文为大家介绍其中的第48题：2n合体，具体如下：
题目描述
等级：容易
知识点：数学
查看题目：2n合体
有一个只包含小写字母n和t的字符串s(1<=|s|<=1000000)，其中如果有两个n相邻，那么它们可以合并成一个m，现在需要你去求这个字符串中，含有多少个'mtm'这样的子序列。
输入一行字符串s；
输出这个字符串中所包含的mtm子序列的个数。
示例1
输入：
"nnntnnn"
输出：
4
解题思路
两个位置容易出现理解问题。
1、子序列。子序列不要求一定是连续的。例如 abcdef的子序列可以是abc，也可以是ace。
2、含有多少个’mtm’这样的子序列。这里不是说先判断如何合并，然后在合并后的字符串上判断mtm子序列有多少个。
题中的含义是这样的（感觉题干确实没说清楚），每次挑两对2n合并成m，然后判断有多少个子序列，之后再挑选不同的2n。所以示例中的答案是4种，而不是1种。
有了上面的解释，理解题干就没有问题了。
求解思路：对于每一个t进行单独考虑，计算这个t的左侧和右侧分别可以合成出多少种不同的m，这两个数的乘积就是对于这个t来说的mtm子序列的个数。
因为只有相邻的n才可以合成m，所以t将原来的字符串分成了一系列n的串。
例如：nnntnnnntnntnnn
被分成了nnn nnnn nn nnn
没有段包含的m个数分别为2 3 1 2
对于每个t来说的mtm子序列就分别是2*（3+1+2） 、（2+3）*（1+2）、 （2+3+1）*2；所以结果为12+15+12 = 39
时间复杂度为O(2*n) 第一次遍历算出每一段m个数，第二次遍历求和；
空间复杂度O(n) 保存每一段m个数
看完之后是不是有了想法了呢，快来练练手吧>>查看题目：2n合体
