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:
- Given S = “aabab”, the function should return 3, because a string “aabaabaa” can be made.
- Given S = “dog”, the function should return 8, because a string “aadaaoaagaa” can be made.
- Given S = “aa”, the function should return 0, because no longer string can be made.
- 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
- 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
