*3K*

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.

## 2 comments

Thanks for the explanation. I understood it better with the help of the video. Please, can you help solve the “Special String Again” question on Hacker

rank

Thank you for your requestâ€¦I will try to add the explanation soon.

Comments are closed.