Min Steps to Make Piles Equal Height Solution

Max Inserts to Obtain String Without 3 Consecutive ‘a’ Microsoft OA 2023

by

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

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

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

Also See: Amazon OA Online Assessment 2023 Questions and Answers

SOLUTION

Program: Max Inserts to Obtain String Without 3 Consecutive ‘a’ Solution in 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: Max Inserts to Obtain String Without 3 Consecutive ‘a’ Solution in 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;
}

Microsoft Online Assessment 2023 Questions List

Leave a Comment

3 × 1 =