Repeat String Infinitely – Return Count of Specific Character Within N Length of Infinite String – JavaScript

Tags: , ,



Trying to solve this HackerRank challenge:

Lilah has a string, s, of lowercase English letters that she repeated infinitely many times.

Given an integer, n, find and print the number of letter a’s in the first letters of Lilah’s infinite string.

For example, if the string s = abcac and n = 10, the substring we consider is abcacabcac, the first 10 characters of her infinite string. There are 4 occurrences of “a” in the substring.

I wrote:

function repeatedString(s, n) {

    s = s.repeat(n);
    s = s.slice(0, n);
    
    let array = Array.from(s);
    let count = 0;
    for (let i = 0; i < array.length; i++) {
        let char = array[i];
        if (char.match(/[a]/gi)) {
            count++;
        }
    }
    return count;
}
console.log(repeatedString("abcac", 10)); 

But HackerRank does not like s = s.repeat(n);, apparently:

enter image description here

I’m not sure how else to generate a string of an appropriate length to slice from. s = s.repeat(Infinity) does not work, and s is not already repeated an infinite number of times when it’s passed in as a parameter.

I.e. console.logging(s), initially, logs

abcac

In this case.

I also tried:

function repeatedString(s, n) {

  let j = n;
  let newString = "";
  while (n > 0) {
      newString += s;
      n--;
  }
  
  newString = newString.slice(0, j);
  let count = 0;
  let array = Array.from(newString);
 
  for (let i = 0; i < array.length; i++) {
      let char = array[i];
      if (char.match(/[a]/gi)) {
          count++;
      }
  }
  return count;
}
console.log(repeatedString("abcac", 10)); 

But this caused a timeout error.

Any other ideas for how to create a string of valid length to slice from?

EDIT:

Constraints:

1 <= |s| <= 100

1 <= n <= 10^12

For 25% of the test cases, n <= 10^6

Answer

actually repeating the string n times is a tremendous waste of memory and runtime.

just compute how often the entire string would be repeated times how many as the string has plus the number of as in the part of s.slice(0, n%s.length)

And your runtime goes down to s.length instead of n

function repeatedString(s, n) {
  var r = n % s.length,
    m = (n - r) / s.length,
    count = 0;

  for (var i = 0; i < s.length; ++i) {
    if (s[i] === "a") {
      count += m + (i < r);
    }
  }
  return count;
}

console.log(repeatedString("abcac", 1234567890));


Source: stackoverflow