Max Inserts to Obtain String Without 3 Consecutive ‘a’

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

Leave a Comment