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