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
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.