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