javascriptalgorithmdata-structures

Hackerrank Repeated String infinite loop problem


I am solving this hackerrank problem for counting the number of 'a's in a given string.

My solution was to store the string in a pattern variable. While the length of the pattern is less than n, it will just add the string to itself. Then I would loop over the pattern and add the number of 'a's in the string.

This solution works fine when n < 1000000. But add one more 0 and when n = 10000000, I get a RangeError for my string in hackerrank because it's too damn long.

Is there a way to get around this RangeError problem? I know there are other ways to solve this problem, but I just want to know how I could edit my code to make it pass the hackerrank test.

function repeatedString(s, n) {
  let pattern = s;
  let count = 0;
  while (pattern.length < n) {
    pattern += pattern;
  }
  for (let i = 0; i < n; i++) {
    if (pattern[i] === 'a') {
      count++;
    }
  }
  return count;
}

Solution

  • You could do math on this rather than consume the memory and calculation on string concatenation and loop

    The total number of a would be the number of a in s times the repeated number of s that has total length not exceed n, plus the remainder (left substring) of s that fill the n

    For example, with the input

    s = 'aba'
    n = 10
    

    It could be simply visually in the below

     aba  aba  aba   a(ba)
    |______3______| |1|
    

    First 3 repeated of aba equals n divided by length of s (i.e 10 / 3 = 3)

    The leftover a (skips bc to equals with n) is the result of s sliced with the length equals remainder of n divided by length of s (i.e 10 % 3 = 1)

    Plus two of these then we get the result

    numberOfA(s) * (n div len(s)) + numberOfA(substr(s, 0, n mod len(s)))
    

    function repeatedString(s, n) {
      const numberOfA = str => str.split('').filter(char => char === 'a').length
      return (
        numberOfA(s) * Math.floor(n / s.length) +
        numberOfA(s.substring(0, n % s.length))
      )
    }
    
    console.log(repeatedString('aba', 10))
    console.log(repeatedString('a', 1000000000000))