Home Strings [Hackerrank] – Repeated String Solution

[Hackerrank] – Repeated String Solution

by nikoo28
0 comment

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.

figure showing sample test case
Fig: 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.

frequency of letter 'a' in repeated string
Fig: Frequency of letter a in repeated string

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
example of counting full repetitions in a repeated string
Fig: Counting the number of full repetitions
  • 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.
remaining characters in a repeated string
Fig: Finding the remaining characters after repetitions

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:

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More