Dada una string binaria str de tamaño N , la tarea es encontrar la longitud de la subsecuencia más pequeña de modo que después de borrar la subsecuencia, la string resultante sea la string continua no decreciente más larga.
Ejemplo :
Entrada: str = “10011”
Salida: 1
Explicación: La eliminación de la primera aparición de ‘1’ da como resultado una subsecuencia no decreciente, es decir, “0011”.Entrada: str = “11110000”
Salida: 4
Enfoque: El problema se puede resolver con base en las siguientes observaciones:
Las subsucesiones no decrecientes pueden ser de los siguientes 3 tipos:
- Caso 1: 00000…..
- Caso 2: 11111…..
- Caso 3: 0000….111111….
Siga los pasos dados para resolver el problema:
- Iterar sobre los caracteres de la string.
- Cuente el número de 0 s y 1 s presentes en la string
- Para generar subsecuencias no decrecientes de la forma «0000…», las eliminaciones mínimas requeridas son el conteo de 1 s en la string
- Para generar subsecuencias no decrecientes de la forma «1111…», las eliminaciones mínimas requeridas son el conteo de 0 s en la string
- Para generar subsecuencias no decrecientes de la forma “0000…1111….”, las eliminaciones mínimas requeridas se pueden obtener siguiendo los siguientes pasos:
- Iterar sobre los caracteres de la string. Considere eliminar los 1 de la izquierda y los 0 del extremo derecho de la string.
- Actualice el mínimo después de cada iteración.
- Finalmente, imprima las remociones mínimas obtenidas en los tres casos anteriores como la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the
// length of smallest subsequence
// required to be removed to make
// the given string non-decreasing
int min_length(string str)
{
// Length of the string
int n = str.length();
// Count of zeros and ones
int total_zeros = 0;
int total_ones = 0;
// Traverse the string
for (int i = 0; i < n; i++) {
if (str[i] == '0')
total_zeros++;
else
total_ones++;
}
// Count minimum removals to
// obtain strings of the form
// "00000...." or "11111..."
int ans = min(total_zeros, total_ones);
int cur_zeros = 0, cur_ones = 0;
for (char x : str) {
// Increment count
if (x == '0')
cur_zeros++;
else
cur_ones++;
// Remove 1s and remaining 0s
ans = min(ans, cur_ones
+ (total_zeros - cur_zeros));
}
cout << ans;
}
// Driver Code
int main()
{
string str = "10011";
min_length(str);
return 0;
}
Java
// Java program for
// the above approach
import java.io.*;
class GFG
{
// Function to return the
// length of smallest subsequence
// required to be removed to make
// the given string non-decreasing
public static void min_length(String str)
{
// Length of the string
int n = str.length();
// Count of zeros and ones
int total_zeros = 0;
int total_ones = 0;
// Traverse the string
for (int i = 0; i < n; i++) {
if (str.charAt(i) == '0'){
total_zeros++;
}
else{
total_ones++;
}
}
// Count minimum removals to
// obtain strings of the form
// "00000...." or "11111..."
int ans = Math.min(total_zeros, total_ones);
int cur_zeros = 0, cur_ones = 0;
for (int i = 0; i<str.length(); i++)
{
// Increment count
char x = str.charAt(i);
if (x == '0'){
cur_zeros++;
}
else{
cur_ones++;
}
// Remove 1s and remaining 0s
ans = Math.min(ans, cur_ones
+ (total_zeros - cur_zeros));
}
System.out.println(ans);
}
// Driver Code
public static void main (String[] args)
{
String str = "10011";
min_length(str);
}
}
// This code is contributed by rohitsingh07052
Python3
# Python3 program for # the above approach # Function to return the # length of smallest subsequence # required to be removed to make # the given string non-decreasing def min_length(str): # Length of the string n = len(str) # Count of zeros and ones total_zeros = 0 total_ones = 0 # Traverse the string for i in range(n): if (str[i] == '0'): total_zeros += 1 else: total_ones += 1 # Count minimum removals to # obtain strings of the form # "00000...." or "11111..." ans = min(total_zeros, total_ones) cur_zeros = 0 cur_ones = 0 for x in str: # Increment count if (x == '0'): cur_zeros += 1 else: cur_ones += 1 # Remove 1s and remaining 0s ans = min(ans, cur_ones + (total_zeros - cur_zeros)) print(ans) # Driver Code if __name__ == '__main__': str = "10011" min_length(str) # This code is contributed by SURENDRA_GENGWAR.
C#
// C# program for
// the above approach
using System;
class GFG{
// Function to return the
// length of smallest subsequence
// required to be removed to make
// the given string non-decreasing
public static void min_length(string str)
{
// Length of the string
int n = str.Length;
// Count of zeros and ones
int total_zeros = 0;
int total_ones = 0;
// Traverse the string
for(int i = 0; i < n; i++)
{
if (str[i] == '0')
{
total_zeros++;
}
else
{
total_ones++;
}
}
// Count minimum removals to
// obtain strings of the form
// "00000...." or "11111..."
int ans = Math.Min(total_zeros, total_ones);
int cur_zeros = 0, cur_ones = 0;
for(int i = 0; i < str.Length; i++)
{
// Increment count
char x = str[i];
if (x == '0')
{
cur_zeros++;
}
else
{
cur_ones++;
}
// Remove 1s and remaining 0s
ans = Math.Min(ans, cur_ones +
(total_zeros - cur_zeros));
}
Console.WriteLine(ans);
}
// Driver code
static public void Main()
{
string str = "10011";
min_length(str);
}
}
// This code is contributed by offbeat
Javascript
<script>
// Javascript program for
// the above approach
// Function to return the
// length of smallest subsequence
// required to be removed to make
// the given string non-decreasing
function min_length(str)
{
// Length of the string
var n = str.length;
// Count of zeros and ones
var total_zeros = 0;
var total_ones = 0;
// Traverse the string
for (var i = 0; i < n; i++) {
if (str[i] == '0')
total_zeros++;
else
total_ones++;
}
// Count minimum removals to
// obtain strings of the form
// "00000...." or "11111..."
var ans = Math.min(total_zeros, total_ones);
var cur_zeros = 0, cur_ones = 0;
for( var i =0; i< str.length; i++){
// Increment count
if (str[i] == '0')
cur_zeros++;
else
cur_ones++;
// Remove 1s and remaining 0s
ans = Math.min(ans, cur_ones
+ (total_zeros - cur_zeros));
}
document.write( ans);
}
// Driver Code
var str = "10011";
min_length(str);
</script>
Producción
1
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por deveshkumarsharma y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA