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: a
a
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
- Maximal Network Rank Solution
- Min Deletions To Obtain String in Right Format
- Day of week that is K days later Solution
- Minimum Adjacent Swaps to Make Palindrome Solution
- Lexicographically Smallest String
- Longest Substring Without Two Contiguous Occurrences of Letter
- String Without 3 Identical Consecutive Letters
- Microsoft OA Longest Semi-Alternating Substring
- Microsoft OA Min Steps to Make Piles Equal Height
- Max Inserts to Obtain String Without 3 Consecutive ‘a’
- Concatenated String Length with unique Characters
- Largest K such that both K and -K exist in array
- Microsoft OA Min Adj Swaps to Group Red Balls
- Maximum Length of a Concatenated String with Unique Characters
- Microsoft OA Unique Integers That Sum Up To 0
- Find N Unique Integers Sum up to Zero
- Microsoft OA Particle Velocity Solution
- Microsoft OA Arithmetic Slices Solution
- Microsoft OA Widest Path Without Trees Solution
- Microsoft OA Jump Game Solution
- Microsoft OA Fair Indexes Solution