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’

Write a function solution that, given a string S consisting of N characters, 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 3 consecutive letters ‘a’. If string S already contains the substring “aaa”, then your function should return -1.

Examples:

1. Given S = “aabab”, the function should return 3, because a string “aabaabaa” can be made.

2. Given S = “dog”, the function should return 8, because a string “aadaaoaagaa” can be made.

3. Given S = “aa”, the function should return 0, because no longer string can be made.

4. Given S= “baaaa”, the function should return -1, because there is a substring “aaa”.

Also See: Microsoft Online Assessment Questions and Solution

Example 1:

Input: aabab

Output: 3

Explanation:

A string aabaabaa can be made

Example 2:

Input: egg

Output: 8

Explanation:

A string aaeaagaagaa can be made

Example 3:

Input: aa

Output: 0

Explanation:

No longer string can be made.

Example 4:

Input: uaaaa

Output: -1

Explanation:

There is a substring aaa

Solution

Program Python:

Max Inserts to Obtain String Without 3 Consecutive ‘a’ in Python is very similar to the logic we applied in C++, but in python we used groupby function to make is easier to count the letters.

from itertools import groupby
n=input()
c=0
flg='#'
for i,j in groupby(n):
    l=len(list(j))
    if i=='a':
        if l<3:
            c+=2-l
        else:
            print(-1)
    else:
        c+=2*(l-(flg=='a'))
    flg=i
c+=2*(n[-1]!='a')
print(c)

Program C++:

If N is number of chars in the given string and all chars are not ‘a’ we can insert into this string 2 * (N + 1)
chars because we can insert two As between of each two chars in the string and two As to the begin and
to the end of the string.

Thus in order to solve this task we need to count all non A chars. When we will know this number it will be easy to calculate how many As we can add. This number will be 2 * (number of possible places to insert + 1) – number of found As In other words 2 * (N + 1) – (N – number of As)

#include <iostream>
#include <string>
using namespace std;
int solution(const string & s) {
    int count_As = 0, count_others = 0, s_len = s.length();
    for (int 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);
}

int main() {

    cout << solution("aabab") << " Expected: 3" << endl;
    cout << solution("dog") << " Expected: 8" << endl;
    cout << solution("aa") << " Expected: 0" << endl;
    cout << solution("baaaa") << " Expected: -1" << endl;

    return 0;
}

Also See: AMCAT Study Materials, Preparation Guide

Also See: Amazon OA Online Assessment 2021 Questions and Answers

Microsoft Online Assessment 2021 Questions

Max Inserts to Obtain String Without 3 Consecutive ‘a’

Solution

Leave a Comment Cancel reply