Dada una string binaria S de longitud N , la tarea es encontrar el número mínimo de caracteres necesarios para eliminar de la string de modo que no exista ninguna subsecuencia de la forma «0101» en la string.
Ejemplos:
Entrada: S = “0101101”
Salida: 2
Explicación: La eliminación de S[1] y S[5] modifica la string a 00111. Por lo tanto, no se puede obtener ninguna subsecuencia del tipo 0101 de la string dada.Entrada: S = “0110100110”
Salida: 2
Enfoque: siga los pasos a continuación para resolver el problema:
- La string válida requerida puede consistir en un máximo de tres bloques de los mismos elementos, es decir, las strings pueden ser uno de los siguientes patrones “00…0”, “11…1”, “00…01…1”, “1…10. .0”, “00..01…10..0”, “1…10…01…1” .
- Cuente las frecuencias de 0 s y 1 s de un bloque usando la suma parcial.
- Fije los índices de inicio y fin de los bloques de 0 s y 1 s y determine el número mínimo de caracteres que deben ser eliminados por las sumas parciales calculadas .
- Por lo tanto, verifique la longitud de la string más larga que se puede obtener eliminando las subsecuencias del tipo dado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find minimum characters
// to be removed such that no subsequence
// of the form "0101" exists in the string
int findmin(string s)
{
int n = s.length();
int i, j, maximum = 0;
// Stores the partial sums
int incr[n + 1] = { 0 };
for (i = 0; i < n; i++) {
// Calculate partial sums
incr[i + 1] = incr[i];
if (s[i] == '0') {
incr[i + 1]++;
}
}
for (i = 0; i < n; i++) {
for (j = i + 1; j < n; j++) {
// Setting endpoints and
// deleting characters indices.
maximum
= max(maximum, incr[i] + j - i + 1
- (incr[j + 1] - incr[i])
+ incr[n] - incr[j + 1]);
}
}
// Return count of deleted characters
return n - maximum;
}
// Driver Code
int main()
{
string S = "0110100110";
int minimum = findmin(S);
cout << minimum << '\n';
}
Java
// Java Program to implement
// the above approach
import java.io.*;
class GFG{
// Function to find minimum
// characters to be removed
// such that no subsequence
// of the form "0101" exists
// in the string
static int findmin(String s)
{
int n = s.length();
int i, j, maximum = 0;
// Stores the partial sums
int[] incr = new int[n + 1];
for (i = 0; i < n; i++)
{
// Calculate partial sums
incr[i + 1] = incr[i];
if (s.charAt(i) == '0')
{
incr[i + 1]++;
}
}
for (i = 0; i < n; i++)
{
for (j = i + 1; j < n; j++)
{
// Setting endpoints and
// deleting characters indices.
maximum = Math.max(maximum, incr[i] +
j - i + 1 -
(incr[j + 1] - incr[i]) +
incr[n] - incr[j + 1]);
}
}
// Return count of
// deleted characters
return n - maximum;
}
// Driver Code
public static void main(String[] args)
{
String S = "0110100110";
int minimum = findmin(S);
System.out.println(minimum);
}
}
// This code is contributed by akhilsaini
Python3
# Python3 Program to implement # the above approach # Function to find minimum # characters to be removed # such that no subsequence # of the form "0101" exists # in the string def findmin(s): n = len(s) maximum = 0 # Stores the partial sums incr = [0] * (n + 1) for i in range(0, n): # Calculate partial sums incr[i + 1] = incr[i] if (s[i] == '0'): incr[i + 1] = incr[i + 1] + 1 for i in range(0, n + 1): for j in range(i + 1, n): # Setting endpoints and # deleting characters indices. maximum = max(maximum, incr[i] + j - i + 1 - (incr[j + 1] - incr[i]) + incr[n] - incr[j + 1]) # Return count of # deleted characters return n - maximum # Driver Code if __name__ == "__main__": S = "0110100110" minimum = findmin(S) print(minimum) # This code is contributed by akhilsaini
C#
// C# Program to implement
// the above approach
using System;
class GFG{
// Function to find minimum
// characters to be removed
// such that no subsequence
// of the form "0101" exists
// in the string
static int findmin(string s)
{
int n = s.Length;
int i, j, maximum = 0;
// Stores the partial sums
int[] incr = new int[n + 1];
for (i = 0; i < n; i++)
{
// Calculate partial sums
incr[i + 1] = incr[i];
if (s[i] == '0')
{
incr[i + 1]++;
}
}
for (i = 0; i < n; i++)
{
for (j = i + 1; j < n; j++)
{
// Setting endpoints and
// deleting characters indices.
maximum = Math.Max(maximum, incr[i] +
j - i + 1 -
(incr[j + 1] - incr[i]) +
incr[n] - incr[j + 1]);
}
}
// Return count of
// deleted characters
return n - maximum;
}
// Driver Code
public static void Main()
{
string S = "0110100110";
int minimum = findmin(S);
Console.WriteLine(minimum);
}
}
// This code is contributed by akhilsaini
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find minimum characters
// to be removed such that no subsequence
// of the form "0101" exists in the string
function findmin(s)
{
let n = s.length;
let i, j, maximum = 0;
// Stores the partial sums
var incr = new Array(n+1);
incr.fill(0);
for (i = 0; i < n; i++) {
// Calculate partial sums
incr[i + 1] = incr[i];
if (s[i] == '0') {
incr[i + 1]++;
}
}
for (i = 0; i < n; i++) {
for (j = i + 1; j < n; j++) {
// Setting endpoints and
// deleting characters indices.
maximum
= Math.max(maximum, incr[i] + j - i + 1
- (incr[j + 1] - incr[i])
+ incr[n] - incr[j + 1]);
}
}
// Return count of deleted characters
return n - maximum;
}
// Driver Code
let S = "0110100110";
let minimum = findmin(S);
document.write(minimum + '\n');
</script>
Producción:
3
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por aaryaverma112 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA