# Max Inserts to Obtain String Without 3 Consecutive ‘a’

Page Contents

Microsoft Online Assessment, Max Inserts to Obtain String Without 3 Consecutive ‘a’

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

Also See: Microsoft Online Assessment Questions and Solution

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`

## Solution

Program Python:

```from itertools import groupby
def max_inserts(s: str) -> int:
ans, last = 0, '#'
for c, g in groupby(s):
L = len(list(g))
if c == 'a':
if L < 3:
ans += 2 - L
else:
return -1
else:
ans += 2 * (L - (last == 'a'))
last = c
ans += 2 * (s[-1] != 'a')
return ans
if __name__ == '__main__':
s = input()
res = max_inserts(s)
print(res)```

Program Java:

```import java.util.Scanner;
class Solution {
public static int maxInserts(String s) {

int count_As = 0;
int count_others = 0;
int s_len = s.length();
for (int i = 0; i < s_len; ++i) {
if (s.charAt(i) == 'a') {
count_As++;
} else {
count_others++;
count_As = 0;
}
if (count_As == 3) {
return -1;
}
}
return 2 * (count_others + 1) - (s_len - count_others);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
scanner.close();
int res = maxInserts(s);
System.out.println(res);
}
}```

Program C++:

```function maxInserts(s) {

let count_As = 0;
let count_others = 0;
const s_len = s.length;
for (let i = 0; i < s_len; ++i) {
if (s[i] === 'a') {
count_As++;
} else {
count_others++;
count_As = 0;
}
if (count_As === 3) {
return -1;
}
}
return 2 * (count_others + 1) - (s_len - count_others);
}
function* main() {
const s = yield;
const res = maxInserts(s);
console.log(res);
}
class EOFError extends Error {}
{
const gen = main();
const next = (line) => gen.next(line).done && process.exit();
let buf = '';
next();
process.stdin.setEncoding('utf8');
process.stdin.on('data', (data) => {
const lines = (buf + data).split('\n');
buf = lines.pop();
lines.forEach(next);
});
process.stdin.on('end', () => {
buf && next(buf);
gen.throw(new EOFError());
});
}```

Also See: AMCAT Study Materials, Preparation Guide

Also See: Amazon OA 2021 (Online Assessment) Questions Preparation

Microsoft Online Assessment 2021 Questions