需求：

• 字符串中连续最多的字符，以及次数
• 如输入 'abbcccddeeee1234'，计算得到：
• 连续最多的字符是 'e'， 4次

方案1 - 传统思路

• 嵌套循环，找出每个字符的连续次数，并记录
• 看似时间复杂度是 O(n^2)
• 但实际时间复杂度是 O(n)，因为有跳步

代码演示

/**
 * 获取连续最多的字符 - 嵌套循环
 * @return [char, count]
 */
export const findContinueChar1 = (
  str: string
): [string, number] => {
  let char = '';
  let count = 0;
  const len = str.length;
  if (!len) return [char, count];

  let tempLen = 0;

  for (let i = 0; i < len; i++) {
    // 每次重置记数
    tempLen = 0;
    for (let j = i; j < len; j++) {
      // 字符相同增加记数
      if (str[i] === str[j]) {
        tempLen += 1;
      }

      // 字符变化 或 j 循环到字符串末尾
      if (str[i] !== str[j] || j === len - 1) {
        if (tempLen > count) {
          char = str[i];
          count = tempLen;
        }
        
        // 跳步 必须控制i的大小否则死循环
        if (i < len - 1) {
          i = j - 1;
        }

        break;
      }
    }
  }

  return [char, count];
}

方案2 - 双指针

• 定义指针 i 和 j。j 不动， i 继续移动
• 如果 i 和 j的值一直相等，则i继续移动
• 直到 i 和 j 的值不相等，记录处理，让 j 追上 i。继续第一步

代码演示

/**
 * 获取连续最多的字符 - 双指针
 * @return [char, count]
 */
export const findContinueChar2 = (
  str: string
): [string, number] => {
  let char = '';
  let count = 0;
  const len = str.length;

  if (!len) return [char, count];

  let i = 0;
  let j = 0;
  let tempCount = 0;

  for (; i < len; i++) {
    const si = str[i];
    const sj = str[j];
    // 字符相同增加记数
    if (si === sj) {
      tempCount ++;
    }
    // 字符不同或已循环到末尾
    if (si !== sj || i === len - 1) {
      if (tempCount > count) {
        count = tempCount;
        char = sj;
      }
      // 重置记数
      tempCount = 0;

      if (i < len - 1) {
        // 让 j 追上 i
        j = i;
        i --;
      }
    }
  }

  return [char, count];
}

功能测试

export const findContinueCharFunctionalTest = () => {
  const str = 'aaa';
  const res = findContinueChar2(str);
  console.log(res); // ['a', 3]
};

单元测试

/**
 * @description 查找最大连续字符
 */
import { findContinueChar2 } from '../src/utils/find-continue-char';

describe('获取连续次数最多的字符', () => {
  test('正常情况', () => {
    const str = '123aaabbb34eeeeff';
    const res = findContinueChar2(str);
    expect(res).toEqual(['e', 4]);
  });
  test('空字符串', () => {
    const str = '';
    const res = findContinueChar2(str);
    expect(res).toEqual(['', 0]);
  });
  test('无连续字符', () => {
    const str = 'abcd';
    const res = findContinueChar2(str);
    expect(res).toEqual(['a', 1]);
  });
  test('全是连续字符', () => {
    const str = 'aaaa';
    const res = findContinueChar2(str);
    expect(res).toEqual(['a', 4]);
  });
});

执行 yarn jest

 PASS  tests/find-continue-char.test.ts
  获取连续次数最多的字符
    ✓ 正常情况 (89 ms)
    ✓ 空字符串
    ✓ 无连续字符 (11 ms)
    ✓ 全是连续字符 (9 ms)

性能测试

export const findContinueCharPerformanceTest = () => {
  let str = '';
  for (let i = 0; i < 100 * 10000; i++) {
    str += i.toString();
  }
  console.time('findChar1');
  findContinueChar1(str);
  console.timeEnd('findChar1');

  console.time('findChar2');
  findContinueChar2(str);
  console.timeEnd('findChar2');
}

执行结果：

• findChar1：117 毫秒
• findChar2：104 毫秒

两种实现方式耗时基本相同，时间复杂度都是 O(n)

其它可选方式

• 正则表达式 - 效率非常低
• 累计各个元素的连续长度，最后求最大值 - 徒增空间复杂度

注意实际复杂度，不要被代码表面迷惑，双指针常用于解决嵌套循环，算法题慎用正则表达式（实际工作中可以用），算法题尽量用 “低级” 代码，慎用语法糖或高级API。