Page Contents

*Microsoft Online Assessment* *Min Deletions To Obtain String in Right Format*

*Microsoft Online Assessment*

*Min Deletions To Obtain String in Right Format*

You are given a string `s`

consisting only of characters `'a'`

and `'b'`

. You can delete any number of characters in `s`

to make `s`

**balanced**. `s`

is **balanced** if there is no pair of indices `(i,j)`

such that `i < j`

and `s[i] = 'b'`

and `s[j]= 'a'`

.

Return *the minimum number of deletions needed to make *

`s`

*.*

**balanced**

Also See: Microsoft Online Assessment Questions and Solution

**Example 1:**

Input:s = "aababbab"Output:2Explanation:You can either: Delete the characters at 0-indexed positions 2 and 6 ("aababbab" -> "aaabbb"), or Delete the characters at 0-indexed positions 3 and 6 ("aababbab" -> "aabbbb").

**Example 2:**

Input:s = "bbaaaaabb"Output:2Explanation:The only solution is to delete the first two characters.

**Constraints:**

`1 <= s.length <= 10`

^{5}`s[i]`

is`'a'`

or`'b'`

.

*Solution*

*Solution*

*Program Python:*

*Two pointer Python O(N) time and O(1) space solution*

The idea is to use two pointers i and j where i traverses from left to right and j traverses from right to left.

While traversing right, get to the first position where s[i] == ‘b’ and similarly while traversing left, get to the first position where s[j] == ‘a’. We also keep on adjusting the count of ‘a’ and ‘b’ accordingly. Now we reach to a point where s[0:i] is all ‘a’ and s[j+1:] is all ‘b’. At this point we need to decide whether we want to delete ‘a’ or ‘b’. So we go greedy and delete that char whose count is less. So if count_a < count_b, we delete char ‘a’ else we delete char ‘b’.

def get_a_count(word): count = 0 for ch in word: if ch == 'a': count += 1 return count def get_minimum_deletions(word): result = 0 i = 0 j = len(word)-1 count_a = get_a_count(word) count_b = len(word)-count_a while i < j: # get to the point where word[i] = 'b' while i < j and word[i] == 'a': i += 1 count_a -= 1 # get to the point where word[j] = 'a' while i < j and word[j] == 'b': j -= 1 count_b -= 1 # we go greedy here and delete that char whose count is less if count_a != 0 and count_b != 0: if count_a < count_b: j -= 1 # simulates deletion of 'a' result += 1 count_a -= 1 else: i += 1 # simulates deletion of 'b' result += 1 count_b -= 1 return result

*Program C++:*

**Logic:**

Scan the string from left to right

1. drop all sequences of the same chars longer than 2;

2. count length of sequences of different chars;

3. save length of the longest sequence.

**Algorithm:**

We should have a counter of the same chars and index which points to the last two chars of this sequence. Lets call them “count” and “start”. And we should have two variable where we will save length of the longest sequence of different chars and index which points to the beginning of this sequence. Lets call them “max_length” and “start_ml”.

So the algorithm in general.

Scan the string from left to right:

0. Take next char of the string;

1.1 If next char is the same as the previous one increase counter of the same chars “count”;

1.2 If next char is different drop counter of the same chars “count” to 1;

2 If number of previous the same chars is:

2.1 More than 2. Move pointer to the beginning of the current sequence of different chars “start” to the previous char before the current one, to keep only two the same chars at the beginning of the sequence.

drop counter of the same chars “count” to 2.

2.2. Less or equal 2. Check if current sequence of different chars is longer than current maximum. If yes — update maximum to the current length. Save pointer to the beginning of the new longest sequence.

3. Go to phase 0.

#include <iostream> #include <vector> using namespace std; string solution(const string &s) { int s_size = s.size(); // start position and length of the longest sequence // which doesn't contain 3 contiguous occurrences of a and b int start_ml = 0, max_length = 0; int start = 0; // start of current processing string of the same letters. int count = 1; // length of current processing string of the same letters. for (int i = 1; i < s_size; ++i) { if (s[i] == s[i - 1]) { // if we met two the same letters increase the counter of the same letters count++; } else { // if next letter is different drop the counter to 1 count = 1; } if (count <= 2) { // if the sequence of different letters continuing, set it's current length as // max_length if it is bigger than current max_length // "i - start + 1" is length of the current processed sequence if (i - start + 1 > max_length) { max_length = i - start + 1; start_ml = start; } } else { // if the sequence of the same letters continuing, // move the pointer to points to the last two chars of this sequence // drop the count to 2 start = i - 1; count = 2; } } return s.substr(start_ml, max_length); } int main() { cout << "Result: " << solution("aabbaabbaabbaa") << " Expected: aabbaabbaabbaa" << endl; cout << "Result: " << solution("aabbaaaaabb") << " Expected: aabbaa" << endl; return 0; }

*Program Java:*

class Solution { public int minimumDeletions(String s) { int n=s.length(); int []dp=new int[n+1]; int bcount=0; for(int i=0;i<n;i++){ char c=s.charAt(i); if(c=='a'){ dp[i+1]=Math.min(dp[i]+1,bcount); }else{ dp[i+1]=dp[i]; bcount++; } } return dp[n]; } }

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*