El número máximo de bits establecidos cuenta en una substring de tamaño K de una string binaria

Posted on by Rudeus Greyrat

Dada una string binaria S de tamaño N y un entero K . La tarea es encontrar el número máximo de bits establecidos que aparecen en una substring de tamaño K.

Ejemplos: 

Entrada: S = “100111010”, K = 3 
Salida: 3 
Explicación: 
La substring “111” contiene 3 bits establecidos.

Entrada: S = “0000000”, K = 4 
Salida: 0 
Explicación: S no tiene bits establecidos, por lo que ans es 0. 
 

Enfoque ingenuo:  

  1. Genere todas las substrings de tamaño K .
  2. Encuentre el máximo de conteo de bits establecidos en todas las substrings.

Complejidad temporal: O( N 2 ).  
Espacio Auxiliar: O(1).

Enfoque eficiente: el problema se puede resolver utilizando la técnica de ventana deslizante.  

  1. Tome la variable maxcount para almacenar el recuento máximo de bits establecidos y la variable Count para almacenar los bits establecidos de recuento de la ventana actual.
  2. Atraviese la string de 1 a K y calcule el recuento de bits establecidos y guárdelo como maxcount .
  3. Cuerda transversal desde K + 1 hasta la longitud de la cuerda.
  4. En cada iteración, disminuya el conteo si (K – i) th bit está establecido. Aumente el conteo si se establece i -ésimo bit. Compara y actualiza maxcount .
  5. Después de completar el recorrido de la array, finalmente devuelva maxcount.

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

C++

// C++ program to find the maximum
// set bits in a substring of size K
#include<bits/stdc++.h>
using namespace std;
 
// Function that find Maximum number
// of set bit appears in a substring
// of size K.
int maxSetBitCount(string s, int k)
{
    int maxCount = 0, n = s.length();
    int count = 0;
 
    // Traverse string 1 to k
    for(int i = 0; i < k; i++)
    {
         
       // Increment count if
       // character is set bit
       if (s[i] == '1')
           count++;
    }
    maxCount = count;
 
    // Traverse string k+1
    // to length of string
    for(int i = k; i < n; i++)
    {
        
       // Remove the contribution of the
       // (i - k)th character which is no
       // longer in the window
       if (s[i - k] == '1')
           count--;
        
       // Add the contribution of
       // the current character
       if (s[i] == '1')
           count++;
            
       // Update maxCount at for
       // each window of size k
       maxCount = max(maxCount, count);
    }
     
    // Return maxCount
    return maxCount;
}
 
// Driver code
int main()
{
    string s = "100111010";
    int k = 3;
 
    cout << (maxSetBitCount(s, k));
    return 0;
}
 
// This code is contributed by Rajput-Ji

Java

// Java program to find the maximum
// set bits in a substring of size K
import java.util.*;
 
class GFG {
 
    // Function that find Maximum number
    // of set bit appears in a substring
    // of size K.
    static int maxSetBitCount(String s, int k)
    {
 
        int maxCount = 0, n = s.length();
        int count = 0;
 
        // Traverse string 1 to k
        for (int i = 0; i < k; i++) {
            // Increment count if
            // character is set bit
            if (s.charAt(i) == '1')
                count++;
        }
 
        maxCount = count;
 
        // Traverse string k+1
        // to length of string
        for (int i = k; i < n; i++) {
 
            // remove the contribution of the
            // (i - k)th character which is no
            // longer in the window
            if (s.charAt(i - k) == '1')
                count--;
 
            // add the contribution of
            // the current character
            if (s.charAt(i) == '1')
                count++;
 
            // update maxCount at for
            // each window of size k
            maxCount = Math.max(maxCount, count);
        }
 
        // return maxCount
        return maxCount;
    }
    // Driver Program
    public static void main(String[] args)
    {
        String s = "100111010";
        int k = 3;
 
        System.out.println(maxSetBitCount(s, k));
    }
}

Python3

# Python3 program to find the maximum
# set bits in a substring of size K
 
# Function that find Maximum number
# of set bit appears in a substring
# of size K.
def maxSetBitCount(s, k):
 
    maxCount = 0
    n = len(s)
    count = 0
 
    # Traverse string 1 to k
    for i in range(k):
         
        # Increment count if
        # character is set bit
        if (s[i] == '1'):
            count += 1
 
    maxCount = count
 
    # Traverse string k+1
    # to length of string
    for i in range(k, n):
 
        # Remove the contribution of the
        # (i - k)th character which is no
        # longer in the window
        if (s[i - k] == '1'):
            count -= 1
 
        # Add the contribution of
        # the current character
        if (s[i] == '1'):
            count += 1
 
        # Update maxCount at for
        # each window of size k
        maxCount = max(maxCount, count)
 
    # Return maxCount
    return maxCount
 
 
# Driver code
if __name__ == '__main__':
     
    s = "100111010"
    k = 3
 
    print(maxSetBitCount(s, k))
     
# This code is contributed by mohit kumar 29

C#

// C# program to find the maximum
// set bits in a substring of size K
using System;
class GFG {
 
// Function that find Maximum number
// of set bit appears in a substring
// of size K.
static int maxSetBitCount(string s, int k)
{
 
    int maxCount = 0, n = s.Length;
    int count = 0;
 
    // Traverse string 1 to k
    for (int i = 0; i < k; i++)
    {
        // Increment count if
        // character is set bit
        if (s[i] == '1')
            count++;
    }
 
    maxCount = count;
 
    // Traverse string k+1
    // to length of string
    for (int i = k; i < n; i++)
    {
 
        // remove the contribution of the
        // (i - k)th character which is no
        // longer in the window
        if (s[i - k] == '1')
            count--;
 
        // add the contribution of
        // the current character
        if (s[i] == '1')
            count++;
 
        // update maxCount at for
        // each window of size k
        maxCount = Math.Max(maxCount, count);
    }
 
    // return maxCount
    return maxCount;
}
// Driver Program
public static void Main()
{
    string s = "100111010";
    int k = 3;
 
    Console.Write(maxSetBitCount(s, k));
}
}
 
// This code is contributed by Code_Mech

Javascript

<script>
 
// Javascript program to find the maximum
// set bits in a substring of size K
 
// Function that find Maximum number
// of set bit appears in a substring
// of size K.
function maxSetBitCount(s, k)
{
    var maxCount = 0, n = s.length;
    var count = 0;
 
    // Traverse string 1 to k
    for(var i = 0; i < k; i++)
    {
         
       // Increment count if
       // character is set bit
       if (s[i] == '1')
           count++;
    }
    maxCount = count;
 
    // Traverse string k+1
    // to length of string
    for(var i = k; i < n; i++)
    {
        
       // Remove the contribution of the
       // (i - k)th character which is no
       // longer in the window
       if (s[i - k] == '1')
           count--;
        
       // Add the contribution of
       // the current character
       if (s[i] == '1')
           count++;
            
       // Update maxCount at for
       // each window of size k
       maxCount = Math.max(maxCount, count);
    }
     
    // Return maxCount
    return maxCount;
}
 
// Driver code
var s = "100111010";
var k = 3;
document.write(maxSetBitCount(s, k));
 
// This code is contributed by famously.
</script>
Producción: 

3

 

Complejidad temporal: O(N).  
Espacio Auxiliar: O(1).
 

Publicación traducida automáticamente

Artículo escrito por offbeat y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *