连续最多的字符

题目

给一个字符串，找出连续最多的字符，以及次数。
例如字符串 'aabbcccddeeee11223' 连续最多的是 e ，4 次。

传统方式

嵌套循环，找出每个字符的连续次数，并记录比较。

时间复杂度看似是 O(n^2)，因为是嵌套循环。 但实际上它的时间复杂度是 O(n)，因为循环中有跳转。

双指针

画图解释

只有一次循环，时间复杂度是 O(n)

性能测试，发现两者时间消耗一样，循环次数也一样。

其他方式

这个题目网上还有其他的答案

• 正则表达式 —— 正则表达式的效率非常低，可进行性能测试（代码 x-reg.ts ）
• 使用数组累计各个字符串的长度，然后求出最大值 —— 增加空间复杂度，面试官不会喜欢

【注意】算法尽量用基础代码实现，尽量不要用现成的 API 或语法糖 —— 方便，但你不好直观判断时间复杂度

答案

上述两种方式（嵌套循环和双指针）都可以，参考 continuous-char.ts

划重点

• 注意实际的时间复杂度，不要被代码所迷惑
• 双指针的思路（常用于解决嵌套循环）