Repeated String
Category: Warm-up Challenges
Difficulty: Easy
Find the number of a's in the first \(n\) letters of an infinitely repeating string.
Input: a string \(s\) of lowercase English letters, and \(n\), the length of the substring to consider when \(s\) is repeated infinitely.
Output: the number of a's in the first \(n\) characters of the infinitely repeating string generated by \(s\).
\(n\) can be a very large number, so you cannot store the entire \(n\)-length substring to count the number of a's. However, we know the substring will contain \(\lfloor \frac{n}{|s|} \rfloor\) complete instances of \(s\), and then the remainder will be the first \(k = n \bmod |s|\) characters of \(s\). Count the number of a's in the first \(k\) characters of \(s\), as well as the number of a's in all of \(s\), and you can calculate the number of a's in the \(n\) characters generated by repeating \(s\).
Java 8:
public static long repeatedString(String s, long n) {
long fullCount = n / s.length();
int partial = (int) (n % s.length());
int count = 0;
int partialCount = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == 'a') {
if (i < partial) {
partialCount++;
}
count++;
}
}
return fullCount * count + partialCount;
}
C++:
long repeatedString(string s, long n) {
const long fullCount = n / s.size();
const int part = n % s.size();
int count = 0;
int partialCount = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] == 'a') {
if (i < part) {
partialCount++;
}
count++;
}
i++;
}
return fullCount * count + partialCount;
}
Python 3:
def repeatedString(s, n):
full_count = n // len(s)
partial = s[:(n % len(s))]
return full_count * s.count('a') + partial.count('a')