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 n 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.

Read the full problem here: Repeated String

Solution:

Let us consider that sub_str is the input string and str_len is the length of the infinite string we are considering.

When the str_len is less than the length of sub_str, we can easily calculate the number of a’s by iterating over the string.

![Repeated String HackerRank]({{ site.url }}/assets/2020-04-24-Repeated-String-HackerRank/HR_repeated_strings-1.jpg){:class="img-responsive"}

long i = 0;
while (i < str_len)
{
    if (sub_str[i] == 'a')
    {
        count++;
    }
    i++;
}

Now, when the str_len is greater than the length of the sub_str length.

![Repeated String HackerRank]({{ site.url }}/assets/2020-04-24-Repeated-String-HackerRank/HR_repeated_strings-2.jpg){:class="img-responsive"}

First, we will find the number of sub strings (sub_str) in the string we are considering.

long num_sub_str = str_len / sub_str.size();

In many cases, the size of combined sub strings is not the multiple of str_len, so few characters are left out and these characters may contain ‘a’. We have to count these characters.

long remaining_str_len = str_len % sub_str.size();

Now, we need to find the number of a’s in the sub_str. Let count will store number of a’s in the sub_str.

long i = 0;
while (i < sub_str.size())
{
    if (sub_str[i] == 'a')
    {
        count++;
    }
    i++;
}

Multiplying count with the num_sub_str will give us number of a’s in the combined sub strings whose size is less than or equal to str_len and multiple of the size of sub_str. But there are few remaining characters whose count is stored in remaining_str_len. We have to find the occurrence of ‘*a8’ in these characters and increment the count if it is found.

count = count * num_sub_str;

i = 0;
while (i < remaining_str_len)
{
    if (sub_str[i] == 'a')
    {
        count++;
    }
    i++;
}

{% include ads.html %}

C++ Implementation

#include <iostream>
#include <string>

long repeated_string(std::string sub_str, long str_len) {
    long count = 0;
    if (str_len > sub_str.size())
    {
        long num_sub_str = str_len / sub_str.size();
        long remaining_str_len = str_len % sub_str.size();

        long i = 0;
        while (i < sub_str.size())
        {
            if (sub_str[i] == 'a')
            {
                count++;
            }
            i++;
        }

        count = count * num_sub_str;

        i = 0;
        while (i < remaining_str_len)
        {
            if (sub_str[i] == 'a')
            {
                count++;
            }
            i++;
        }
    }
    else
    {
        long i = 0;
        while (i < str_len)
        {
            if (sub_str[i] == 'a')
            {
                count++;
            }
            i++;
        }
    }
    return count;
}

int main()
{
    std::string input_str;
    long final_str_length;

    std::cin >> input_str;
    std::cin >> final_str_length;

    std::cout << repeated_string(input_str, final_str_length) << "\n";

    return 0;
}

View this on Github

If you have another solution then please share it in the comments below.

Repeated String - HackerRank | C++ Implementation

Problem:

Solution:

C++ Implementation

Other Competitive Programming Problems and Solutions