Минимизируйте количество нулей, требуемых для удаления, чтобы максимизировать длину самой длинной подстроки, равной единицам

Опубликовано: 14 Декабря, 2021

Принимая во внимание двоичной строки S длиной N, задача состоит в том, чтобы найти должно быть удалено из заданной строки S , чтобы получить самую длинную подстроку 1s минимального число 0 сек.

Примеры:

Input: S = “010011”
Output: 2
Explanation:
Removing str[2] and str[3] modifies the string S to “0111”. Therefore, the minimum number of removals required is 2.
Input: S = “011111”
Output: 0

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: Идея заключается в том , чтобы найти крайний левый и крайний правый индекс 1 в строке, затем подсчитывает число 0 с настоящим между ними. Наконец, выведите полученное значение счетчика. Выполните следующие действия, чтобы решить проблему:

Просмотрите строку S, чтобы найти первое и последнее вхождение 1 в строке и сохранить его индексы в переменных, скажем, влево и вправо , соответственно.
Итерируйте по диапазону [влево, вправо], используя переменную i , и если значение str [i] равно 0 , увеличивайте счетчик на 1.
После выполнения вышеуказанных шагов выведите значение count в качестве результата.

Ниже представлена реализация описанного выше подхода:

C ++

 // C++ program for the above approach
 #include <bits/stdc++.h>
 using namespace std;
 // Function to count the minimum number
 // of 0s required to be removed to
 // maximize the longest substring of 1s
 void minNumZeros(string str)
 {
    // Stores leftmost and rightmost
    // indices consisting of 1
    int left = INT_MAX, right = INT_MIN; 
    // Stores the count of 0s
    // between left and right
    int count = 0; 
    // Traverse the string str
    for ( int i = 0; i < str.length(); i++) { 
        // If the current character is 1
        if (str[i] == '1' ) { 
            // Update leftmost and rightmost
            // index consisting of 1
            left = min(i, left);
            right = max(right, i);
        }
    }
    // If string consists only of 0s
    if (left == INT_MAX) {
        cout << "0" ;
        return ;
    }
    // Count the number of 0s
    // between left and right
    for ( int i = left; i < right; i++) { 
        if (str[i] == '0' ) {
            count++;
        }
    }
    // Print the result
    cout << count;
 }
 // Driver Code
 int main()
 {
    string str = "010011" ;
    minNumZeros(str);
    return 0;
 }

Джава

 // Java program for the above approach
 import java.io.*;
 class GFG{
 // Function to count the minimum number
 // of 0s required to be removed to
 // maximize the longest substring of 1s
 static void minNumZeros(String str)
 {
    
    // Stores leftmost and rightmost
    // indices consisting of 1
    int left = Integer.MAX_VALUE;
    int right = Integer.MIN_VALUE; 
    // Stores the count of 0s
    // between left and right
    int count = 0 ; 
    // Traverse the string str
    for ( int i = 0 ; i < str.length(); i++)
    {
        
        // If the current character is 1
        if (str.charAt(i) == '1' )
        {
            
            // Update leftmost and rightmost
            // index consisting of 1
            left = Math.min(i, left);
            right = Math.max(right, i);
        }
    }
    // If string consists only of 0s
    if (left == Integer.MAX_VALUE)
    {
        System.out.print( "0" );
        return ;
    }
    // Count the number of 0s
    // between left and right
    for ( int i = left; i < right; i++)
    {
        if (str.charAt(i) == '0' )
        {
            count++;
        }
    }
    // Print the result
    System.out.print(count);
 }
 // Driver Code
 public static void main(String[] args)
 {
    String str = "010011" ;
    
    minNumZeros(str);
 }
 }
 // This code is contributed by Dharanendra LV

Python3

 # Python program for the above approach
 import sys
 # Function to count the minimum number
 # of 0s required to be removed to
 # maximize the longest substring of 1s
 def minNumZeros(st) : 
    # Stores leftmost and rightmost
    # indices consisting of 1
    left = sys.maxsize
    right = - sys.maxsize - 1 
    # Stores the count of 0s
    # between left and right
    count = 0 
    # Traverse the string str
    for i in range ( len (st)) :
    #for (int i = 0; i < str.length(); i++) {
        # If the current character is 1
        if st[i] = = '1' : 
            # Update leftmost and rightmost
            # index consisting of 1
            left = min (i, left)
            right = max (right, i)
        
    # If string consists only of 0s
    if left = = sys.maxsize :
        print ( "0" )
        return
    
    # Count the number of 0s
    # between left and right
    for i in range (left,right):
        
    #for (int i = left; i < right; i++) {
        if st[i] = = '0' :
            count + = 1
        
    # Print the result
    print (count)
 # Driver Code
 if __name__ = = "__main__" :
    st = "010011" ;
    minNumZeros(st)
    
 # This code is contributed by jana_sayantan.

C #

 // C# program for the above approach
 using System;
 class GFG{
 // Function to count the minimum number
 // of 0s required to be removed to
 // maximize the longest substring of 1s
 static void minNumZeros( string str)
 {
    
    // Stores leftmost and rightmost
    // indices consisting of 1
    int left = int .MaxValue;
    int right = int .MinValue; 
    // Stores the count of 0s
    // between left and right
    int count = 0; 
    // Traverse the string str
    for ( int i = 0; i < str.Length; i++)
    {
        
        // If the current character is 1
        if (str[i] == '1' )
        {
            
            // Update leftmost and rightmost
            // index consisting of 1
            left = Math.Min(i, left);
            right = Math.Max(right, i);
        }
    }
    // If string consists only of 0s
    if (left == int .MaxValue)
    {
        Console.WriteLine( "0" );
        return ;
    }
    // Count the number of 0s
    // between left and right
    for ( int i = left; i < right; i++)
    {
        if (str[i] == '0' )
        {
            count++;
        }
    }
    // Print the result
    Console.WriteLine(count);
 }
 // Driver Code
 static public void Main()
 {
    string str = "010011" ;
    
    minNumZeros(str);
 }
 }
 // This code is contributed by Dharanendra LV

Выход:

Сложность времени: O (N)
Вспомогательное пространство: O (1)

Technical Scripter

Минимизируйте количество нулей, требуемых для удаления, чтобы максимизировать длину самой длинной подстроки, равной единицам

C ++

Джава

Python3

C #

РЕКОМЕНДУЕМЫЕ СТАТЬИ