Longest Repeating Character In String - Javascript - Stack Overflow

admin管理员组

文章数量:1356326

I'm ultimately trying to solve this challenge on codewars.

I know how to find out how many times a character appears in a string, but not how many times it appears in order.

I.e. given the string bbbaaabaaaa, we see that the longest repeating character is a of length 4.

I tried a simple for-loop, paring characters to previous characters to see if they're identical:

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'));

I'm ultimately trying to solve this challenge on codewars.

I know how to find out how many times a character appears in a string, but not how many times it appears in order.

I.e. given the string bbbaaabaaaa, we see that the longest repeating character is a of length 4.

I tried a simple for-loop, paring characters to previous characters to see if they're identical:

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'));

What's most concerning is that chunk is not increasing in size ever whenever I console.log it.

Shouldn't we be seeing:

'chunk**' b

'chunk**' bb

'chunk**' bbb

?

Instead, we're just seeing the single characters get logged. Then, my logic is to pare the chunk to the longestChunk and return the longestChunk outside of the for-loop.

Any ideas as to why this isn't working, or what other strategies I should try to return the longest repeating character from a string?

I realize that I will have to format what I return as an array with the character that repeats the most, and the length of it's longest repeat or chunk.

• javascript
• string
• algorithm
• for-loop

Share Improve this question Follow edited Oct 26, 2019 at 19:42 HappyHands31 asked Oct 26, 2019 at 19:15 HappyHands31HappyHands31 4,1011919 gold badges6565 silver badges117117 bronze badges 5

• 3 Your set chunk to an empty string at the beginning of every loop iteration – NineBerry Commented Oct 26, 2019 at 19:25
• 1. you reset chunk at each iteration so it won't increase much. 2. you make a special if case in the for loop. If really necessary, do it outside and start your for loop at i=1. 3. you return a string but spec says only length needed. 4. no need to increment every time just keep track of startingSequenceIndex and when sequence is broken, do the substraction. 5.no need to pare [i] with [i+1], just pare [i] with c (the character given in spec) – grodzi Commented Oct 26, 2019 at 19:26
• 1 You should only empty chunk when the character is different from the previous. – trincot Commented Oct 26, 2019 at 19:27
• Another strategy: github./khaled301/js-excercise-code/blob/leet-code/… – Tiago Peres Commented Oct 26, 2019 at 19:29
• My hint woudl be using a Map object as accumulator and .reduce() function. – Redu Commented Oct 26, 2019 at 19:46

Add a ment  | 

5 Answers 5

Sorted by: Reset to default 4

Here is my solution:

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];
}

console.log(longestRepetition("bbbaaabaaaa"))

Thank you everyone for helping me clean up my code! The key (as @NineBerry pointed out) was to define chunk as an empty string outside of the for-loop, and re-assign chunk as a new, single character when it's different from the previous.

You can simply use a regular expression to find the longest matching single letter sequence:

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

Just play around with the following fiddle:

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>

Just in case you'd want a shorter version of your idea:

function longestRepetition (str) {
  let longestChunk = '';
  let currentChunk = '';
  for(let i = 0; i < str.length; i++){
     if(currentChunk[0] !== str[i]){
        currentChunk = str[i];
     } else {
        currentChunk += str[i];
     }
     if(currentChunk.length > longestChunk.length){
        longestChunk = currentChunk;
     }
  }
  return [longestChunk[0] ?? '', longestChunk.length];
}

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

/** Hello, I have borrowed the idea from the last solution and then customized it to serve my purpose. Credit goes to the contributor. */

function largestConsecRepeatChar(inputStr) {
    let lrgConsRepChar = "";
    if (inputStr && typeof inputStr === 'string' && inputStr.trim()) {
        function reducerCallback(accumulator, currentValue) {
            if (accumulator.lastChar === currentValue) {
                accumulator.count += 1;
            } else {
                accumulator.count = 1;
            }
            accumulator.lastChar = currentValue;
            if (accumulator.count > accumulator.result.countTracker) {
                accumulator.result = { repeatingChar: currentValue, countTracker: accumulator.count };
            } else {
                accumulator.result = accumulator.result;
            }
            return accumulator;
        }
        const initialValue = {
            result: { repeatingChar: "", countTracker: 0 }
        };
        const { result } = inputStr.trim().split('').reduce(reducerCallback, initialValue);
        lrgConsRepChar = result.countTracker > 1 ? result.repeatingChar.repeat(result.countTracker) : "";
        return lrgConsRepChar;
    }
    return lrgConsRepChar;
}

console.log(largestConsecRepeatChar(" ybtyyrjpy "));

You could solve this by using reduce on an array from your string:

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'));

Docs: Array.prototype.reduce().

It obviously depends on use-case but, in general, expect reducers to be cheap to run, as they only go through the collection once.

In this particular case, your solution (the for loop) runs all tests in ~230ms. The reducer function runs them in ~80ms (with slight variations - ran them 3 times each).
The reducer is almost three times faster.

本文标签： Longest Repeating Character In StringJavascriptStack Overflow