Самый длинный повторяющийся символ в строке - Javascript

Question

Я в конечном итоге пытаюсь решить эту проблему на кодовых войнах.

Я знаю, как узнать, сколько раз символ появляется в строке, но не сколько раз он появляется в порядке .

То есть, учитывая строку bbbaaabaaaa, мы видим, что самый длинный повторяющийся символ - a длины 4.

Я попробовал простой цикл for, сравнивая символы с предыдущими символами, чтобы увидеть, идентичны ли они:

function longestRepetition (str) {
  let longestChunk = '';
  for (let i = 0; i < str.length; i++) {
    let chunk = '';
    if (i === 0) {
      if (str[i] === str[i + 1]) {
        chunk += str[i];
      }
    }
    if (i > 0) {
      if (str[i] === str[i - 1]) {
        chunk += str[i];
        console.log('chunk**', chunk);
      }
      if (chunk.length > longestChunk.length) {
        longest = chunk;
      }
    }
  }
  return longestChunk;
}

console.log(longestRepetition('bbbaaabaaaa'));

Что больше всего беспокоит, так это то, что chunk не увеличивается в размерах, когда я console.log это.

Разве мы не должны видеть:

'chunk**' b

'chunk**' bb

'chunk**' bbb

?

Вместо этого мы видим, как одиночные символы получаютжурнал. Затем моя логика - сравнить chunk с longestChunk и вернуть longestChunk за пределами цикла for.

Любые идеи относительно того, почему это не работает, или какие другие стратегииЯ должен попытаться вернуть самый длинный повторяющийся символ из строки?

Я понимаю, что мне придется форматировать то, что я возвращаю, как массив с символом, который повторяется больше всего, и длиной его самого длинного повторения или chunk.

Answer 1

Вот мое решение:

function longestRepetition (str) {
  if (str.length === 0) {
     return ['', 0]
  }
  let longest = '';
  let chunk = '';
  for (let i = 0; i < str.length; i++) {
    if (i === 0) {
      if (str[i] === str[i + 1]) {
        chunk += str[i];
      }
    }
    if (i > 0) {
      if (str[i] === str[i - 1]) {
        chunk += str[i];
        console.log('chunk**', chunk);
      }
      if (str[i] !== str[i - 1]) {
        chunk = str[i];
      }
      if (chunk.length > longest.length) {
        longest = chunk;
      }
    }
  }
  return [longest[0], longest.length];
}

Спасибо всем за помощь в очистке моего кода! Ключ (как указал @NineBerry) состоял в том, чтобы определить чанк как пустую строку вне цикла for, и переназначить чанк как новый отдельный символ, если он отличается от предыдущего.

Answer 2

Вы можете просто использовать регулярное выражение, чтобы найти самую длинную соответствующую последовательность из одной буквы:

str.match(/(.)\1*/g).sort((a,b)=>b.length-a.length)[0]

Просто поиграйте со следующей скрипкой:

document.querySelector('#test').addEventListener('keyup',function(ev){
 var res=(ev.target.value.match(/(.)\1*/g)||['']).sort((a,b)=>b.length-a.length)[0];
 document.querySelector('#out').innerText=JSON.stringify([res[0],res.length]);
});

<input size="40" type="text" id="test" value="aaaabbbbbbbccddddzfffffklxxxaavvvv"><br>
<div id="out"></div>

Answer 3

Вы можете решить эту проблему, используя Reduce для массива из вашей строки:

function longestRepetition(s) {
  const reducer = (acc, value) => {
    acc.count = acc.last === value
      ? acc.count + 1
      : 1;
    acc.last = value;
    acc.result = acc.count > acc.result.count
      ? { count: acc.count, char: value }
      : acc.result;
    return acc;
  }
  const initAcc = {
    result: {
      char: '',
      count: 0
    }
  }
  const { result } = s.split('').reduce(reducer, initAcc);
  
  return [result.char, result.count];
}

console.log(longestRepetition('aaabbbabbaaaabba'));

Документы: Array.prototype.reduce () .

Это, очевидно, зависит от варианта использования, но, в общем, ожидайте, что редукторы будут дешевыми, поскольку они проходят сбор только один раз.

В этом конкретном случае ваше решение (цикл for) запускает все тесты в ~230ms. Функция редуктора запускает их в ~80ms (с небольшими отклонениями - запускает их по 3 раза каждый).
Редуктор работает почти в три раза быстрее.