Federico Pintaluba
I'm a 27 years old developer, I have been coding for more than a decade, but I have focused in Android Development for the past 5 years. Here you will find all my projects, ideas, thoughts. Basically everything I made with <3.

HackerRank: Repeated String (O(n) approach)

Problem

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 a occurrences of a in the substring.

Function Description

Complete the repeatedString function in the editor below. It should return an integer representing the number of occurrences of a in the prefix of length n in the infinitely repeating string.

repeatedString has the following parameter(s):

  • s: a string to repeat
  • n: the number of characters to consider

Input Format

The first line contains a single string, s.
The second line contains an integer, n.

Constraints

Output Format

Print a single integer denoting the number of letter a‘s in the first n letters of the infinite string created by repeating  infinitely many times.

Sample Input 0

aba
10

Sample Output 0

7

Explanation 0
The first n = 10 letters of the infinite string are abaabaabaa. Because there are 7 a‘s, we print 7 on a new line.

Sample Input 1

a
1000000000000

Sample Output 1

1000000000000

Explanation 1
Because all of the first n = 1000000000000 letters of the infinite string are a, we print 1000000000000 on a new line.

Solution

The solution is pretty straightforward, let’s make a quick solution and then look for improvements.

I will do a while loop, iterating over the s string size, while is less than n, sum the string until we surpass the n value, and then substring that from 0 to n.

    var newS = ""

    while (newS.length < n) {
        newS += s
    }

    newS = newS.substring(0, n)
    return newS.count { it == 'a' }.toLong()

If we run the sample input:

aba
10

We get

7

Woohoo! We made it…

OH WAIT, we have a second interesting case, n = 1000000000000, we will definitely go out of memory, or get our return string two days from now.

We need to think of another solution, but following what we already did, the solution is there, but is taking FOREVER for the second case.

Clearly, our first aproas is exponential, the less lenght the string has and the higher de n gets, it’s taking more and more time, we need to think something that could take constant time, whatever we throw at it, this is known in Big O annotation as O(n), let’s go for it.

Let’s find out first, how many times our strings repeats over to reach n, we can easily do this by dividing n over the string length.

val repeats = n.div(s.length)

We know that our string get repeated at least repeats times.

Remember that Int operations discard the fractional part, so we have some characters left over, we need to find them, and it’s pretty easy, let’s find that with the Modulus operator, this by definition will give us the remainder of the division, so let’s declare a val for that.

val leftOver = (n % s.length).toInt()

Now we now how many characters we left over on our first division.

Do we really need to count the amount of ‘a’ in the whole final string as we did in the first case? That’s just non-sense, let’s do it from the origin string and then we can multiply this by repeats, without discarding the left over, let’s do this.

val perString = s.count { it == 'a' }

We have easily found how many ‘a’ we have in the original string, but we are missing the remaining characters, let’s find those.

val remainder = s.take(leftOver).count { it == 'a' }

A quick way to substring is the take() function for CharSequence, this will substring from 0 to n, or return the whole string if n is greater than the string length. After getting what was left over, we get how many ‘a’ there are in there.

Finally, we return the original string ‘a’ count, multiplied by repeated, and we finally sum our remainder.

return repeats.times(perString).plus(remainder)

Now we have it, no matter how big it gets, this will be done in the same amount of time.

We ended with something shorter and way more efficient that our last attempt:

fun repeatedString(s: String, n: Long): Long {
    val repeats = n.div(s.length)
    val leftOver = (n % s.length).toInt()
    val perString = s.count { it == 'a' }
    val remainder = s.take(leftOver).count { it == 'a' }
    return repeats.times(perString).plus(remainder)
}

Let’s submit this code to HackerRank and see if we pass all the test cases!

All 22 test cases passed, we are good now!

Hope this helped you understand a fair solution made in Kotlin for this problem, if you have any suggestion or a better way of doing this in the same language, don’t hesistate on commenting below!

Share

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *