统计字符串中连续重复字符个数的实用方法

【出自BD笔试题】

难度系数：★★★★☆ 被考察系数：★★★☆☆

题目描述：

用递归的方法实现一个求字符串中连续出现相同字符的最大值，例如字符串“aaabbcc”中连续出现字符‘a’的最大值为3，字符串“abbc”中连续出现字符‘b’的最大值为2。

分析与解答：

如果不要求采用递归法，那么算法的实现就非常简单，只需要在遍历字符串的时候定义两个额外的变量curMaxLen与maxLen，分别记录与当前遍历的字符重复的连续字符的个数和遍历到目前为止找到的最长的连续重复字符的个数。在遍历的时候，如果相邻的字符相等，则执行curMaxLen+1；否则，更新最长连续重复字符的个数，即maxLen=max（curMaxLen，maxLen），由于碰到了新的字符，因此curMaxLen=1。

题目要求用递归的方法来实现，通过对非递归方法进行分析可以知道，在遍历字符串的时候，curMaxLen与maxLen是最重要的两个变量，那么在进行递归调用的时候，通过传入两个额外的参数（curMaxLen与maxLen）就可以采用与非递归方法类似的方法来实现，实现代码如下：(www.xing528.com)

程序的运行结果如下：

abbc的最长连续重复子串长度为：2

aaabbcc的最长连续重复子串长度为：3

算法性能分析：

由于这种方法对字符串进行了一次遍历，因此算法的时间复杂度为O（N）。这种方法也没有申请额外的存储空间。