Coding Challenges, A different way to think (JavaScript)

As a bootcamp grad, one of the greatest weaknesses I had coming fresh from the curriculum was Data Structures and Algorithms. As such, some coding challenges that were more like this and ‘riddle type’ concepts were harder for me than more practical concepts like setting up a backend, filtering data, or creating a feature in the frontend. Today I want to go over a particular practice code challenge I solved that stood out to me.

This is the problem: https://www.hackerrank.com/challenges/repeated-string/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=warmup

Essentially, the premise is given an input s and n, where they are a string and number respectively, find the number of a’s in the string where the number is the total number of characters in the string. For example, if the string is ‘abba’ and the number is 11, then how many a’s are there in the new string ‘abbaabbaabb’.

My first code attempt is where I create a new string of length n based of the original string. Then I split the new string into an array and go through each element of the array to check if the element is an ‘a’. And finally returning the number of a’s in the string. My function looked as such:

function repeatedString (s, n){
    let counter = n / s.length
    counter = Math.floor(counter)
    counter -= 1

    let remainder = n % s.length
    let string = s
    let list = s.split('')

    for (counter; counter !== 0;){
        string += s
        counter -= 1
    }

    let splitString = string.split('')

    for (let i = 0; i !== remainder;){
        splitString.push(list[i])

        i += 1
    }

    let letterACounter = 0

    splitString.forEach(e => {
        if(e === 'a'){
            letterACounter += 1
        }
    })

    return letterACounter
}

The function works, but the run time is horrendous, especially for longer inputs. For example, try using the following as the input:

let sample = 'a'
let iterations = 1000000000000

console.log(repeatedString(sample, iterations))

Either it takes a long time to run or eventually it’ll break because it takes too long. Instead I had to use another appraoch.

I realized that the iteration number and the length of a string were important and that I could take a mathematical approach to this. Simply, I realized that I could divide the iteration amount by the length of the string and multiply that by the number of a’s in the original string. The one drawback is when the iteration amount isn’t a multiple of the length of the string. So I had to also keep track of the remainder in those cases and then run through the string the remainder amount of times. Here is the code for this try:

function repeatedString(s, n){
    let countOfA = 0
    let splitS = s.split('')
    let remains = n % s.length

    let times = n / s.length
    times = Math.floor(times)

    splitS.forEach(e => {
        if(e === 'a'){
            countOfA += 1
        }
    });

    countOfA = countOfA * times

    for(let i = 0; i != remains; i++){
        if(splitS[i] === 'a'){
            countOfA += 1
        }
    }

    return countOfA
}

Perfect! It runs much much faster, remains accurate, and looks cleaner as well!

Conclusion

It’s important to take a step back from a problem and simply take a different look at the problem. In this case, I first tried to dive head first and hard code for loops and forEach methods. Taking a more methodical approach using math and simple logic proved to work and also helped understand the problem much better.