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

Given a string S, returns 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 made

Example 2:

Input: dog

Output: 8

Explanation:

A string aadaaoaagaa can be made

Example 3:

Input: aa

Output: 0

Explanation:

No longer string can be made.

Example 4:

Input: baaaa

Output: -1

Explanation:

There is a substring aaa

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