frontend-interview

Appearance

每日一题 - 找出字符串中连续出现最多的字符和个数 ​

信息卡片 ​

  • 时间：2019-07-30
  • tag：字符串 连续

题目描述 ​

找出字符串中连续出现最多的字符和个数。

比如：

"abcaakjbb" => {"a":2,"b":2 }
"abbkejsbcccwqaa" => {"c":3 }
"abcaakjbb" => {"a":2,"b":2 }
"abbkejsbcccwqaa" => {"c":3 }

思路 ​

连续的题目有一些比较通用的思路，就是不断和前面或者后面的元素进行比较， 然后不断更新结果。

我们来试着简化一下题目来发现一下本质问题， 我们把题目改成“找出字符串中连续出现字符最多的个数”

我们可以写出如下代码：

js
function MRC(str) {
  if (str.length === 0) return 0;
  let max = 1;
  let count = 1;

  for (let i = 1; i < str.length; i++) {
    if (str[i] === str[i - 1]) {
      count++;
    } else {
      max = Math.max(max, count);
      count = 1;
    }
  }

  return max;
}
function MRC(str) {
  if (str.length === 0) return 0;
  let max = 1;
  let count = 1;

  for (let i = 1; i < str.length; i++) {
    if (str[i] === str[i - 1]) {
      count++;
    } else {
      max = Math.max(max, count);
      count = 1;
    }
  }

  return max;
}

我们继续将这个pattern扩展到题目就很容易写出类似下面的代码：

参考代码 ​

js
function MRC(str) {
  if (str.length === 0) return {};
  str = str + "$";
  let count = (max = 1);
  let maxKeys = [str[0]];

  for (let i = 1; i < str.length; i++) {
    const pre = str[i - 1];
    if (str[i] === pre) {
      count++;
    } else {
      if (count > max) {
        maxKeys = [pre];
        max = count;
      } else if (count === max) {
        maxKeys.push(pre);
      }
      count = 1;
    }
  }

  return maxKeys.reduce((acc, k) => ((acc[k] = max), acc), {});
}
function MRC(str) {
  if (str.length === 0) return {};
  str = str + "$";
  let count = (max = 1);
  let maxKeys = [str[0]];

  for (let i = 1; i < str.length; i++) {
    const pre = str[i - 1];
    if (str[i] === pre) {
      count++;
    } else {
      if (count > max) {
        maxKeys = [pre];
        max = count;
      } else if (count === max) {
        maxKeys.push(pre);
      }
      count = 1;
    }
  }

  return maxKeys.reduce((acc, k) => ((acc[k] = max), acc), {});
}