Maximice la suma de los pesos asignados cambiando como máximo K bits en una string binaria dada

Dada una string binaria str de longitud N y un número entero K , la tarea es encontrar la suma máxima posible de pesos asignados que se pueden obtener cambiando como máximo K bits en la string binaria dada. El peso asignado a los caracteres de esta string es el siguiente:

• Si un carácter es ‘0’ , entonces el peso es 0 .
• Si un carácter es ‘1’ y el carácter que lo precede también es ‘1’ , entonces el peso es 2 .
• Si un carácter es ‘1’ y no hay ningún carácter antes de él o el carácter que lo precede es ‘0’ , entonces el peso es 1 .

Ejemplos:

Entrada: str = “10100”, K = 2
Salida: 7
Explicación:
1er giro: Voltear el carácter en el índice 1, la string se convierte en “11100”.
2do giro: Voltear el carácter en el índice 3, la string se convierte en «11110».
El peso de la string resultante es 1 + 2 + 2 + 2 + 0 = 7, que es el máximo.

Entrada: str = “100101”, K = 1
Salida: 6
Explicación:
1er giro: Voltear el carácter en el índice 5, la string se convierte en “100111”.
El peso de la string resultante es 1 + 0 + 0 + 1 + 2 + 2 = 6, que es el máximo.

Enfoque: El peso del carácter ‘1’ que aparece después de un ‘1’ es mayor entre todos los caracteres, por lo tanto, para maximizar la suma, intente crear tantos 1 como sea posible. Los segmentos de 0 que se cambiarán a 1 se pueden priorizar de la siguiente manera:

• Primera prioridad: voltee todos los 0 encerrados entre dos 1 , esto aumentaría el peso del segmento de la forma 10…01 en (2*(número de 0 encerrados) + 1). Si x es mayor o igual que el número de 0 encerrado en otro caso por 2*(número de 0 encerrado).
• Segunda prioridad” Invierta 0 al comienzo de la string que precede a la primera aparición de 1 en la string, esto aumentaría el peso del segmento de forma 0… 01 en 2* (número de 0 invertidos).
• Tercera prioridad: cambiar 0 al final de la string después de la última aparición de 1 en la string, esto aumentaría el peso del segmento de forma 10…0 en 2* (número de 0 invertidos).

Voltee el carácter de la string dada según la prioridad anterior para maximizar el peso y luego encuentre el peso de la string resultante después de que K voltea como máximo. 

A continuación se muestra la implementación de este enfoque:

// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find maximum sum of
// weights of binary string after
// at most K flips
int findMax(string s, int n, int k)
{
    int ans = 0;
 
    // Stores lengths of substrings
    // of the form 1..00..1s
    int l = 0;
 
    // Stores the index of last 1
    // encountered in the string
    int ind = -1;
 
    // Stores the index of first 1
    // encountered
    int indf = -1;
 
    // Stores lengths of all substrings
    // having of 0s enclosed by 1s
    // at both ends
    multiset<int> ls;
 
    // Traverse the string
    for (int i = 0; i < n; i++) {
        // If character is 0
        if (s[i] == '0')
            l++;
 
        // If character is 1
        // First Priority
        else if (s[i] == '1'
                 && l > 0 && ans != 0) {
            ls.insert(l);
            l = 0;
        }
 
        // Second Priority
        if (s[i] == '1') {
            ind = i;
            l = 0;
            if (indf == -1)
                indf = i;
 
            // Add according to the
            // first priority
            if (i > 0 && s[i - 1] == '1')
                ans += 2;
            else
                ans += 1;
        }
    }
 
    // Stores length of the shortest
    // substring of 0s
    int curr;
 
    // Convert shortest substrings
    // of 0s to 1s
    while (k > 0 && !ls.empty()) {
        curr = *ls.begin();
 
        // Add according to the
        // first priority
        if (k >= curr) {
            ans += (2 * curr + 1);
            k -= curr;
        }
 
        // Add according to the
        // third priority
        else {
            ans += (2 * k);
            k = 0;
        }
        ls.erase(ls.begin());
    }
 
    // If more 0s can be made into 1,
    // then check for 0s at ends
    if (k > 0) {
        // Update the ans
        ans += (2 * min(k,
                        n - (ind + 1))
                - 1);
        k -= min(k, n - (ind + 1));
 
        if (ind > -1)
            ans++;
    }
 
    // If K is non-zero, then flip 0s
    // at the beginning
    if (k > 0) {
        ans += (min(indf, k) * 2 - 1);
 
        if (indf > -1)
            ans++;
    }
 
    // Return the final weights
    return ans;
}
 
// Driver Code
int main()
{
    // Given string str
    string str = "1110000101";
 
    int N = str.length();
 
    // Given K flips
    int K = 3;
 
    // Function Call
    cout << findMax(str, N, K);
 
    return 0;
}

# Python 3 program of the above approach
 
# Function to find maximum sum of
# weights of binary string after
# at most K flips
def findMax( s, n, k):
 
    ans = 0;
 
    # Stores lengths of substrings
    # of the form 1..00..1s
    l = 0;
 
    # Stores the index of last 1
    # encountered in the string
    ind = -1;
 
    # Stores the index of first 1
    # encountered
    indf = -1;
 
    # Stores lengths of all substrings
    # having of 0s enclosed by 1s
    # at both ends
    ls = set([])
 
    # Traverse the string
    for i in range(n):
        # If character is 0
        if (s[i] == '0'):
            l+=1
 
        # If character is 1
        # First Priority
        elif (s[i] == '1'
                 and l > 0 and ans != 0):
            ls.add(l);
            l = 0;
 
        # Second Priority
        if (s[i] == '1') :
            ind = i;
            l = 0;
            if (indf == -1):
                indf = i;
 
            # Add according to the
            # first priority
            if (i > 0 and s[i - 1] == '1'):
                ans += 2;
            else:
                ans += 1;
 
    # Stores length of the shortest
    # substring of 0s
    curr = 0
 
    # Convert shortest substrings
    # of 0s to 1s
    while (k > 0 and len(ls)!=0):
        for i in ls:
          curr = i
          break
 
        # Add according to the
        # first priority
        if (k >= curr):
            ans += (2 * curr + 1);
            k -= curr;
 
        # Add according to the
        # third priority
        else :
            ans += (2 * k);
            k = 0;
        
        ls.remove(curr);
     
    # If more 0s can be made into 1,
    # then check for 0s at ends
    if (k > 0) :
        # Update the ans
        ans += (2 * min(k,
                        n - (ind + 1))
                - 1);
        k -= min(k, n - (ind + 1));
 
        if (ind > -1):
            ans+=1
 
    # If K is non-zero, then flip 0s
    # at the beginning
    if (k > 0):
        ans += (min(indf, k) * 2 - 1);
 
        if (indf > -1):
            ans+=1
    
    # Return the final weights
    return ans
 
# Driver Code
if __name__ == "__main__":
   
    # Given string str
    s = "1110000101";
 
    N = len(s)
 
    # Given K flips
    K = 3;
 
    # Function Call
    print(findMax(s, N, K));
 
    # This code is contributed by chitranayal

14

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