Best solutions for Microsoft interview tasks. Min Deletions To Obtain String in Right Format.

Description:

We are given a string S of length N consisting only of letters ‘A’ and/or ‘B’. Our goal is to obtain a string in the format “A…AB…B” (all letters A’ occur before all letters ‘B’) by deleting some letters from S. In particular, strings consisting only of letters A’ or only of letters ‘B* fit this format.

Solution:

Actually we need to find an equilibrium point on this string where most of ‘A’ letters will be placed on the left from this point and most of ‘B’ letters on the right. The simplest solution for all cases is to remove all ‘B’ or ‘A’ letters. But we can’t accept it because it doesn’t fit to criteria “the minimum number of letters that need to be deleted”. So we need to find a point such that if we remove the minimum number of letters A on the left, and the minimum number of letters B on the right, we get a string in the format “A … AB … B”. For example if we have given string “AABBB” this point is between “AA” and “BBB” and we don’t need to remove any letters. For string AABABBB there are two such points because we may convert the string to right format by removing single ‘A’ or ‘B’. We may find any of these points.

int solution(const string & s) {
const char CHAR_A = 'A';
int num_Bs = 0, min_dels = 0;
for(auto c : s) {
if (CHAR_A == c) {
//minimum deletions with this character included
//is equal to count of all Bs before it
min_dels = min(num_Bs, min_dels + 1);
}
else {
num_Bs++;
// there is no need to exclude the last B at the end of
// the string, the min_dels does not change
}
}
return min_dels;
}

Looking for an interesting project to join. https://www.linkedin.com/in/molchevsky/