Best solutions for Microsoft interview tasks. Max Inserts to Obtain String Without 3 Consecutive 'a'

Description:

Solution:

If N is number of characters in the given string and all characters are not A we can insert into this string 2 * (N + 1) characters, because we can insert two As between of each two characters 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 instert. 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);

C++ code:

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);
}        

Repository with the full project you can find here: https://github.com/jolly-fellow/microsoft/tree/master/max_inserts_to_obtain_string_without_3_consecutive_a

Return to the table of contents.