Recuento de operaciones para liberar una string binaria «ab»

Dada una string que contiene solo los caracteres ‘a’ y ‘b’. Convierta la string dada en una string en la que no haya una substring ‘ab’. Para liberar la string ‘ab’, podemos realizar una operación en la que seleccionamos una substring ‘ab’ y la reemplazamos por ‘bba’. 
Encuentre el número total de operaciones requeridas para convertir la string dada.

Ejemplos: 

Input : s = 'abbaa'
Output : 2
Explanation:
Here, ['ab'baa] is replaced s = [bbabaa]
[bb'ab'aa] is replaced s = [bbbbaaa]
which is ab free. Hence, 2 operations required.

Input : s = 'aab'
Output : 3
Explanation:
Here, [a'ab'] is replaced s = [abba]
['ab'ba] is replaced s = [bbaba]
[bb'ab'a] is replaced s = [bbbbaa]
which is ab free. Hence, 3 operations required.

Enfoque: El estado final será algún carácter ‘a’ después de ‘b’: “bbb…baaa…a” 
Es obvio demostrar que todas las ‘b’ son distintivas entre sí (es decir, cada ‘b’ en el estado inicial, agregará algunos número de ‘b’s al estado final disjunto de otras ‘b’s). Para un carácter ‘b’ desde el estado inicial, se duplicará después de ver un carácter ‘a’. Para cada i -ésimo carácter ‘b’, considere t _i el número de a antes de él. Entonces, el número final de ‘b’ se puede definir como la suma de 2^t _i .

A continuación se muestra la implementación del enfoque anterior. 

//code to make 'ab' free string
 
#include<bits/stdc++.h>
using namespace std;
 
// code to make 'ab' free string
int abFree(string s)
{
    int n = s.length();
    char char_array[n + 1];
     
    // convert string into char array
    strcpy(char_array, s.c_str());
     
    // Traverse from end. Keep track of count
    // b's. For every 'a' encountered, add b_count
    // to result and double b_count.
    int b_count = 0;
    int res = 0;
    for (int i = 0; i < n; i++)
    {
        if (char_array[n - i - 1] == 'a')
        {
            res = (res + b_count);
            b_count = (b_count * 2);
        } else {
            b_count += 1;
        }
    }
    return res;
}
 
// Driver code
int main()
{
    string s = "abbaa";
    cout<<abFree(s)<<endl;
     
    s = "aab";
    cout<<abFree(s)<<endl;
     
    s = "ababab";
    cout<<abFree(s)<<endl;
     
    return 0;
}
 
// This code is contributed by Rajput-Ji

//code to make 'ab' free string
import java.util.*;
 
class GFG
{
 
    // code to make 'ab' free string
    static int abFree(char[] s)
    {
 
        // Traverse from end. Keep track of count
        // b's. For every 'a' encountered, add b_count
        // to result and double b_count.
        int b_count = 0;
        int res = 0;
        for (int i = 0; i < s.length; i++)
        {
            if (s[s.length - i - 1] == 'a')
            {
                res = (res + b_count);
                b_count = (b_count * 2);
            } else {
                b_count += 1;
            }
        }
        return res;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        String s = "abbaa";
        System.out.println(abFree(s.toCharArray()));
 
        s = "aab";
        System.out.println(abFree(s.toCharArray()));
 
        s = "ababab";
        System.out.println(abFree(s.toCharArray()));
    }
}
 
// This code is contributed by Princi Singh

# code to make 'ab' free string
def abFree(s):
    
    # Traverse from end. Keep track of count
    # b's. For every 'a' encountered, add b_count
    # to result and double b_count.
    b_count = 0
    res = 0
    for i in range(len(s)):
        if s[~i] == 'a':
            res = (res + b_count)
            b_count  = (b_count  * 2)
        else:
            b_count  += 1
    return res
 
# driver code
s = 'abbaa'
print(abFree(s))
 
s = 'aab'
print(abFree(s))
 
s ='ababab'
print(abFree(s))

//code to make 'ab' free string
using System;
using System.Collections.Generic;
 
class GFG
{
 
    // code to make 'ab' free string
    static int abFree(char[] s)
    {
 
        // Traverse from end. Keep track of count
        // b's. For every 'a' encountered, add b_count
        // to result and double b_count.
        int b_count = 0;
        int res = 0;
        for (int i = 0; i < s.Length; i++)
        {
            if (s[s.Length - i - 1] == 'a')
            {
                res = (res + b_count);
                b_count = (b_count * 2);
            } else
            {
                b_count += 1;
            }
        }
        return res;
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        String s = "abbaa";
        Console.WriteLine(abFree(s.ToCharArray()));
 
        s = "aab";
        Console.WriteLine(abFree(s.ToCharArray()));
 
        s = "ababab";
        Console.WriteLine(abFree(s.ToCharArray()));
    }
}
 
// This code contributed by Rajput-Ji

<script>
// code to make 'ab' free string
function abFree(s)
{
    var n = s.length;
     
    // convert string into char array
    var char_array = s.split('')
     
    // Traverse from end. Keep track of count
    // b's. For every 'a' encountered, add b_count
    // to result and double b_count.
    var b_count = 0;
    var res = 0;
    for (var i = 0; i < n; i++)
    {
        if (char_array[n - i - 1] == 'a')
        {
            res = (res + b_count);
            b_count = (b_count * 2);
        } else {
            b_count += 1;
        }
    }
    return res;
}
 
// Driver code
var s = "abbaa";
document.write( abFree(s) + "<br>");
 
s = "aab";
document.write( abFree(s) + "<br>");
 
s = "ababab";
document.write( abFree(s) + "<br>");
 
 
</script>

Producción:  

2
3
11

Complejidad temporal : O(n) 
Espacio auxiliar : O(n)