Algorithms

HackerRank Repeated String Challenge

Given an integer, n, print the number of letter a in the first n letters of the infinite string

---

The details for the problem detailed in this post can be found at https://www.hackerrank.com/challenges/repeated-string/problem

The following solution is written in Javascript.

Problem

Write a function that given an integer, n, and a string, s, will find and print the number of letter a's in the first n of the infinite string.

• string s = a string of lowercase English letters that is repeated infinitely many times.
• int n = the first n letters of the infinite string.

Example

The substring we consider is abcacabcac, the first 10 characters of the infinite string. There are 4 occurrences of a in the substring.

Function Description

repeatedString has the following parameter(s):

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

Returns

• int: the frequency of a in the substring

Input Format

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

Constraints & Validation

• s will be between 1 and 100 characters in length
• n will be between 1 and 10^12
• For 25% of test cases, n will be less than or equal to 10^6

    1 <= |s| <= 100
    1 <= n <= 10^12
  

Sample Input 0

    aba
    10
  

Sample Output 0

    7
  

Explanation

The first n = 10 letters of the infinite string are abaabaabaa. Because there are 7 a's, we return 7.

Sample Input 1

    a
    1000000000000
  

Sample Output 0

    1000000000000
  

Explanation

Because all of the first n = 1000000000000 letters of the infinite string are a, we return 1000000000000.

First Attempt

We will first add a statement that will simply return n id the string is 'a'.

    if(s == 'a') return n;
    

We then create the substring by creating an array from the string to loop through.

    let array = s.split(''),
        count = 0,
        aCount = 0,
        substring = '';

        while (count < n) {
            if(newString.length == n) break;
            if(count == array.length) count = 0;
            newString += array[count]
            count++;
        }

Finaly we return the frequency of a in the substring

    return newString.split('a').length-1;;

The full function is as below:

    function repeatedString(s, n) {

        if(s == 'a') return n;

        let array = s.split(''),
            count = 0,
            aCount = 0,
            newString = '';

        while (count < n) {
            if(newString.length == n) break;
            if(count == array.length) count = 0;
            newString += array[count]
            count++;
        }

        return newString.split('a').length-1;;
    }

Although this function worked it failed on a number of test cases due to the Time limit exceeding. The method above is far from optimized and is more of a brute force attempt.

Second Attempt

For my second attempt I decided that instead of using loops I could calculate the frequency of 'a' in s and then calculate how many times the string can be repeated in n.

    let aInString = (s.split('a').length - 1),
        frequency = Math.floor(n/(s.length)) * aInString;
    

One thing to consider here though is the fact that there could be a number of characters remaining after we divide n by the length of s. We can work out how many characters, if any, are left with the modular operator:

    remStringLength = n % s.length;
    

We can now use the slice method to get the actual string remaining and use the split method we've already used to return the frequency of 'a' if there are any in the remaining string and add it to the frequency:

    frequency += (s.slice(0, remStringLength).split('a').length - 1);
    

Final Full Function

    function repeatedString(s, n) {

            if(s == 'a') return n;

            let aInString = (s.split('a').length - 1),
                frequency = Math.floor(n/(s.length)) * aInString,
                remStringLength = n % s.length;

            frequency += (s.slice(0, remStringLength).split('a').length - 1);

            return frequency;
        }