How To Solve The Repeated String Challenge

How To Solve HackerRank’s Repeated String Code Challenge With JavaScript

6 min readJan 4, 2019

How To Solve The Repeated String Code Challenge

Problem

The Repeated String challenge for me seems like taking DNA, duplicating it a piece, and cutting it at specific length. In the case of the string it’s an existing string with a set pattern of characters and copy it X (unknown) amount of times to meet the string length of (N).

Lilah = the person with the string (could be an infinite number of other different names).
S = the string pattern we’re given some occurrences of “a” present
S = Must be between 1 and 100 characters.
N = The string character limit we need to meet.
N = Must be between 1 and 1000000000000
“a” = The letter we need to count the number of occurrences from our extended string pattern

// Example 1
// S = "aba"
// N = 10// "aba"
// "abaaba"
// "abaabaaba"
// "abaabaabaa"// Number of "a", Result: 7// Example 2
// S = "a"
// N = 1000000000000...
// Number of "a", Result: 1000000000000

Goal

Write a function or functions that returns the total number of letter “a”’s found by repeating the pattern (S) up to a length of (N)

Covering Our Bases

Covering our bases is quite simple but we still need to make sure that:

S is a string between 1 and 100
N is an integer, between 1 and 10¹²

function repeatedString(s, n) {
     const min = 1;
     const maxs = 100;
     const maxn = 1000000000000;     if (typeof s === "string"
          && s.length >= min
          && s.length <= maxs
          && n === parseInt(n, 0)
          && n >= min
          && n <= maxn) {
          // continue
     }
}

Understanding The Problem

At first glance, we might just do a for loop and start copies the pattern X amount of times and then just count the number of “a” from there. This would definitely solve the problem but it’s not the most performant. To find this we’ll need to use some math to better find the number of “a”’s represent.

What We Know

// S contains X amount of "a"'s
// S is a length of Y
// S must be multiple M times to match the length of N length// Y x M = N
// Solve for M
// Y/Y x M = N/Y - Divide by Y on both sides
// M = N/Y// Let's try this formula in practice with Example 1
// S = "aba"
// Y = S.length = 3
// N = 10// M = 10/3
// M = 3.3333333333// Unfortunately words can't be multiple 0.3333333333 times
// But we can multiply by 3, which needs to be an integer
// which gives an us indication that there are leftover
// Another way to say leftovers in math is modulus// Let's modify our math solution
// N = parseInt(N / Y) x Y // N = parseInt(10 / 3) x 3 = 9
// 9 != 10, but 9 + 1 (leftover) = 10
// So, now we need the remainder from modulus
// N = (parseInt(N / Y) x Y) + (N % Y)// Using Example 1
// 10 = (parseInt(10 / 3) x 3) + (10 % 3)
// 10 = 9 + 1

So why does this matter? Well, it can multiple the string, we can also multiply the number “a”’s present within S.

Counting A’s

// Example 1
// S = "aba"
// N = 10
// AS = 2 - Number of a's in S
// Expected result: 7// Using our formula
// (parseInt(N / Y) x Y) + (N % Y)
// Replace Y with AS
// (parseInt(N / Y) x AS) + (N % AS)
// (parseInt(10 / 3) x 2) + (10 % 2)
// 6 + 0// Not quite right
// Really what we need is to count the number of "a"'s
// from the remainder S

Getting The Remainder Of A’s

Using Example 1 again:

// Example 1
// S = "aba"
// N = 10
// AS = 2 - Number of a's in S
// Expected result: 7// We now that from our original formula
// (parseInt(N / Y) x AS) + (N % Y)
// changing (parseInt(N / Y) x Y) to (parseInt(N / Y) x AS) is right
// But (N % AS) should really be (N % Y)
 
// Because what (N % Y) is really giving us
// is the remainder of characters left from S
// Another way to write this is
// S.slice(0, (N % Y))
// OR
// S.slice(0, (N % S.length));
// "aba".slice(0, (10 % "aba".length));
// Result: "a"// From that we just need to manually count the number of "a"'s
// But what if N = 11, then
// "aba".slice(0, (11 % "aba".length));
// Result: "ab"// To count the number of "a"'s we just need to remove all the "b"'s
// and count the length of the string
// "ab".replace("b", ""); 
// Result: "a"
// "a".length
// Result: 1

Putting Our Formula Together

// Example 1
// S = "aba"
// N = 10
// AS = 2 - Number of a's in S
// Expected result: 7// Rewriting our formula
// (parseInt(N / Y) x AS) + (N % Y)
// Add our new replace and length
// (parseInt(N / Y) x AS) + S.slice(0, (N % Y)).length// Taking Example 1 and putting in the values
// parseInt(10 / 3) x 2 + "aba".slice(0, (10 % 3)).replace("b", "").length
// 3 x 2 + "a".length
// 6 + 1
// 7 - the expected result

Let’s now convert this into the code we’re given:

function repeatedString(s, n) {
     const min = 1;
     const maxs = 100;
     const maxn = 1000000000000;
     const len = s.length;
     let as = 0;
     if (typeof s === "string"
          && s.length >= min
          && s.length <= maxs
          && n === parseInt(n, 0)
          && n >= min
          && n <= maxn) {          as = (parseInt(n / len) * s.replace("b", "").length);
    
          as += s.slice(0, (n % len)).replace("b", "").length; 
     }
     return as; 
}

Solution

Our final optimized solution, using arrays, because replace looks be costly:

function repeatedString(s, n) {
     const min = 1;
     const maxs = 100;
     const maxn = 1000000000000;
     let as = s.split('').filter(i => i === "a").length;
     if (typeof s === "string"
          && s.length >= min
          && s.length <= maxs
          && n === parseInt(n, 0)
          && n >= min
          && n <= maxn) {
          as = (parseInt(n / s.length, 0) * r) + (s.slice(0, (n % s.length)).split('').filter(i => i === "a").length);
     }
     return as; 
}

UPDATE Oct 24, 2019

Thanks to Carlos Fabian Abreu Valerio for point out a typo in the code. If you were wondering what r was, it’s suppose to be as. So the code for that part should look like this:

as = (parseInt(n / s.length, 0) * as) + (s.slice(0, (n % s.length)).split('').filter(i => i === "a").length);

Test Cases

// S = "aba", N = 10, Expected 7
// S = "a", N = 1000000000000, Expected 1000000000000
// S = "a", N = 1, Expected 1
// S = "bbb", N = 10, Expected 0repeatedString("aba", 10); // 7 ✅
repeatedString("a", 1000000000000); // 1000000000000 ✅
repeatedString("a", 1); // 1 ✅ 
repeatedString("bbb", 10); // 0 ✅

Feedback!

If you have any recommendations on how this can be optimized, or even a better solution, let’s talk. I love feedback.

If you got value from this, please share it on twitter 🐦 or other social media platforms. Thanks again for reading. 🙏

Please also follow me on twitter: @codingwithmanny and instagram at @codingwithmanny.