Microsoft Online Assessment (OA) - Max Inserts to Obtain String Without 3 Consecutive 'a'

Given a string S, return the maximum number of letters a that can be inserted into S (including at the front and end of S) so that the resulting string doesn’t contain three consecutive letters a. If string S already contains the substring aaa, then your function should return -1.

Example 1:

Input: aabab

Output: 3

Explanation:

A string aabaabaa can be created

Example 2:

Input: dog

Output: 8

Explanation:

A string aadaaoaagaa can be created

Example 3:

Input: aa

Output: 0

Explanation:

No longer string can be created because it already contains 'aaa'.

Example 4:

Input: baaaa

Output: -1

Explanation:

Given string contains a substring aaa, hence no additional 'a' can be inserted.

Try it yourself

Implementation

1from itertools import groupby
2
3def max_inserts(s: str) -> int:
4    ans, last = 0, '#'
5    for c, g in groupby(s):
6        L = len(list(g))
7        if c == 'a':
8            if L < 3:
9                ans += 2 - L
10            else:
11                return -1
12        else:
13            ans += 2 * (L - (last == 'a'))
14        last = c
15    ans += 2 * (s[-1] != 'a')
16    return ans
17
18if __name__ == '__main__':
19    s = input()
20    res = max_inserts(s)
21    print(res)
22
1import java.util.Scanner;
2
3class Solution {
4    public static int maxInserts(String s) {
5        int count_As = 0;
6        int count_others = 0;
7        int s_len = s.length();
8        for (int i = 0; i < s_len; ++i) {
9            if (s.charAt(i) == 'a') {
10                count_As++;
11            } else {
12                count_others++;
13                count_As = 0;
14            }
15            if (count_As == 3) {
16                return -1;
17            }
18        }
19        return 2 * (count_others + 1) - (s_len - count_others);
20    }
21
22    public static void main(String[] args) {
23        Scanner scanner = new Scanner(System.in);
24        String s = scanner.nextLine();
25        scanner.close();
26        int res = maxInserts(s);
27        System.out.println(res);
28    }
29}
30
1function maxInserts(s) {
2    let count_As = 0;
3    let count_others = 0;
4    const s_len = s.length;
5    for (let i = 0; i < s_len; ++i) {
6        if (s[i] === 'a') {
7            count_As++;
8        } else {
9            count_others++;
10            count_As = 0;
11        }
12        if (count_As === 3) {
13            return -1;
14        }
15    }
16    return 2 * (count_others + 1) - (s_len - count_others);
17}
18
19function* main() {
20    const s = yield;
21    const res = maxInserts(s);
22    console.log(res);
23}
24
25class EOFError extends Error {}
26{
27    const gen = main();
28    const next = (line) => gen.next(line).done && process.exit();
29    let buf = '';
30    next();
31    process.stdin.setEncoding('utf8');
32    process.stdin.on('data', (data) => {
33        const lines = (buf + data).split('\n');
34        buf = lines.pop();
35        lines.forEach(next);
36    });
37    process.stdin.on('end', () => {
38        buf && next(buf);
39        gen.throw(new EOFError());
40    });
41}
42

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫