Repeated String

See the original problem on HackerRank.

Solutions

Let’s call l the length of the string. Thus, we have copies = n / l copies of the string.

Let’s call occ the number of occurrences of a in the string. Thus, we have at least occ * l occurrences of a.

The extra number of a is calculated from the possible remainder of the first n / l characters in the string. So we calculate the number of a in the first n%l characters.

Here is a C++ solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

string s; long n; 
cin >> s >> n;
int l = s.size();

auto occ = count(begin(s), end(s), 'a');
auto copies = n/l;

const auto remainder = n % l;
const auto aInFirstPart = count(begin(s), next(begin(s), remainder), 'a');

cout << (copies*occ + aInFirstPart);

An alternative solution in Python:

1
2

s, n = input().strip(), int(input().strip())
print(s.count("a") * (n // len(s)) + s[:n % len(s)].count("a"))

This simple exercise gives us the opportunity to find “perturbations” (variations) on the problem. Basically, we start from the problem as-is and we make it more or less complicated.

For example:

• count other letters (take this information from the input)
• search the infinite string with generators
• don’t use loops (only use standard functions or constructs, instead)
• don’t use the module operator