[Hackerrank] – Repeated String Solution

3.2K

Question: Given a string, count the number of times the letter ‘a’ is repeated.

Input: str = “abcac”, n= 10

Output: 4

Let us try to understand this problem statement and its test case first.

You have a string of lowercase English letters, that is repeated infinitely many times. Along with it, you also have a number ‘n’. You need to find out how many times the letter a appears in the first n characters of this infinite string. Let us look at a sample test case.

Upon looking at the test case, it may seem that the length of the original string is only 5 characters, and the value of n is 12. How do you calculate the occurrences then? It is said that the string is repeated an infinite number of times. This simply means that after abcac, you need to repeat this pattern again.

The infinite string thus becomes: abcac abcac abcac abcac abcac...

Once you form this infinite string, simply count how many times you can find the letter a in the first n characters. In the above test case, we find the letter a a total of 5 times.

Method 1:

The brute force method to solve this problem is pretty straight forward.

• Repeat the string n number of times.
• Start iterating from the first letter of the string.
• Count till n characters and every-time you get the letter a increment a counter.
• Return the counter once you traverse n characters.

Method 2:

The above method works perfectly, but it is not an optimized approach, we waste a lot of time just to repeat the string and iterating over all the characters. The problem statement should give you a very obvious hint. It is a repeated string.

This means that we need to somehow take advantage of this recurring property. Let us take up one more test case

str = "abcd"
n = 10

Applying a little bit of mathematics what we can do now is:

• Find the number of occurrences of a in the original string.
• Count the number of times, the entire string is repeated in the first n characters

• Next, you can find the length of the remaining string. ( = n - (string\ length * occurrences\ of\ entire\ string))
• From the remaining length count the number of a in the original string.
• Add the count from remaining length and the repeated string.

Code:

  long repeatedString(String s, long n) {

    long strLength = s.length();

    // Count the number of 'a' in the given string
    int count = 0;
    for (int i = 0; i < strLength; i++) {
      if (s.charAt(i) == 'a') {
        ++count;
      }
    }

    long repeatedTimes = n / strLength;

    // Find the length of string left after repetitions
    long stringLeftLength = n - (strLength * repeatedTimes);

    // Count the remaining repetitions
    int extra = 0;
    for (int i = 0; i < stringLeftLength; i++) {
      if (s.charAt(i) == 'a') {
        ++extra;
      }
    }

    long totalCount = (repeatedTimes * count) + extra;

    return totalCount;
  }
Code language: Java (java)

Time Complexity: O(l) l – length of string
Space Complexity: [O(1)

The code along with the test cases can also be found on Github.

Video Explanation: