arrays - Repeat String Infinitely - Return Count of Specific Character Within N Length of Infinite String - JavaScript - Stack O

admin管理员组

文章数量:1244218

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

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:

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

• javascript
• arrays
• string

Share Improve this question Follow edited Jul 11, 2019 at 15:18 HappyHands31 asked Jul 11, 2019 at 14:57 HappyHands31HappyHands31 4,1011919 gold badges6565 silver badges117117 bronze badges 4

• If s contains "a" 3 times, and s gets repeated four times to be of length n, then the answer is 3 * 4. For n= infinity, that'll be 3 * Infinity, which will result in Infinity... For sure you have to consider were s.length % n !== 0, but thats not too plicated. – Jonas Wilms Commented Jul 11, 2019 at 15:03
• For the second snippet, I'm not getting a timeout error. Is that the case with anybody else? – user11698627 Commented Jul 11, 2019 at 15:05
• @Tuneer causes a timeout error on HackerRank, and all of the answers below do as well. – HappyHands31 Commented Jul 11, 2019 at 15:10
• @JonasWilms added constraints for n in the edit - 1 <= n <= 10^12 – HappyHands31 Commented Jul 11, 2019 at 15:19

Add a ment  | 

7 Answers 7

Sorted by: Reset to default 9

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

just pute 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));

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

I tested this and knows it works. Essentially, I'm not creating a new string, I just find out how many times I have to multiply the original string in order to be able to truncate it. Then I multiply that number by how many a's there were in the original string.

function repeatedString(s, n) {

    var charLength = s.length;
    var repeat = Math.floor(n/charLength);
    var remainder = n%(charLength);
    var strCut = s.slice(0, remainder);
    
    let count = 0;
    let arrayX = Array.from(s);
    for (let i = 0; i < arrayX.length; i++) {
        let char = arrayX[i];
        if (char.match(/[a]/gi)) {
            count++;
        }
    }
    
    count = count * repeat;
    
    let arrayY = Array.from(strCut);
    for (let i = 0; i < arrayY.length; i++) {
        let char = arrayY[i];
        if (char.match(/[a]/gi)) {
            count++;
        }
    }

    return count;
}

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

I tried a small solution with .repeat but as Thomas said, it's expensive and was taking ages to run tests.

function repeatedString(s, n) {
    const allAs = s.match(/a/g);
    if (!allAs) {
        return 0;
    }
    if (s === 'a') {
        return n;
    }
    const reps = s.repeat(Math.ceil(n/s.length)).slice(0, n).match(/a/g)
    if (!reps) return 0;
    return reps.length;
};

console.log(repeatedString('abc', 10));
console.log(repeatedString('abcde', 10));

But I followed Thomas idea and came up with a simpler solution

function repeatedString(s, n) {
    const allAs = s.match(/a/g);
    if (!allAs) {
        return 0;
    }
    if (s === 'a') {
        return n;
    }
    const rem = n % s.length;
    const reps = (n-rem)/s.length;
    let count = reps * allAs.length;
    if (rem) {
        const rest = s.slice(0, rem).match(/a/g);
        if (rest) count = count + rest.length
    }
    return count;
}

console.log(repeatedString('a', 100000));
console.log(repeatedString('abcde', 10000000000));

You could use while loop to repeat original string until length is matched and then match to count the numbers of a.

function repeatedString(s, n) {
  let i = 0, l = s.length;
  while (s.length < n) s += s[i++ % l]
  return s.match(/a/g).length;
}
console.log(repeatedString("abcac", 10));

I did this code and it worked well.

function repeatedString(s, n) {
    let modulus = n % s.length;
    let repetition = (n - modulus) / s.length;
    let remainCounts = s.slice(0, modulus).split("").filter((item) => item == "a").length
    
    return (s.split("").filter((item) => item == "a").length * repetition) + remainCounts
}

enter image description here

Creating an infinite string and calculating is very costly. Instead of that calculating how many times 'a' repeats in the input string and multiple max occurrences can happens seems a good way of doing it.

1. Find the reminder after the original string is repeated as whole in the limit.
2. Find the maximum time input string can fit in the allowed length as whole.
3. count the a's occurrence and multiply by maxCompleteOccur + a' s occurrence in the reminder string.

Used PHP substr_count() to count the number of substring occurrences

function repeatedString($s, $n) {
    
    // Find the reminder after the original string is repeated as whole
    $reminder = $n % (strlen($s)); 


    // Find the maximum time input string can fit in the allowed length
    $maxCompleteOccur = floor($n / strlen($s));



    // count the a's occurance and multiply by maxCompleteOccur + a's occurance in reminder string. 
    return floor(substr_count($s, 'a') * $maxCompleteOccur) + substr_count($s, 'a', 0, $reminder);

}

本文标签：