Repeated String · Coding Gym

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

An alternative solution in Haskell:

1
2
3
4
5
6
7


solve :: String -> Int -> Int
solve s n = rep * ( countA s ) + countA las
  where
    l = length s
    rep = div n l
    las = take ( rem n l ) s
    countA = length . filter (== 'a')

An alternative solution in Rust:

1
2
3
4
5
6
7
8


fn solve(s: &str, n: usize) -> usize {
    let chars_count = s.chars().count();
    let remainder = n % chars_count;
    let repeat = n / chars_count;
    let a_in_s = s.chars().filter(|&c| c == 'a').count();
    let a_in_remainder = s.chars().take(remainder).filter(|&c| c == 'a').count();
    repeat * a_in_s + a_in_remainder
}

In Rust, chars and bytes are different things. If we know the input is an ASCII string, we can optimize the code by iterating the raw buffer:

1
2
3
4
5
6
7
8


fn solve(s: &[u8], n: usize) -> usize {
    let chars_count = s.len();
    let remainder = n % chars_count;
    let repeat = n / chars_count;
    let a_in_s = s.iter().filter(|&&c| c == b'a').count();
    let a_in_remainder = s.iter().take(remainder).filter(|&&c| c == b'a').count();
    repeat * a_in_s + a_in_remainder
}

strings