string binaria str están en
Ejemplos:
Entrada:
Salida:
Explicación:Entrada:
Salida:
Explicación:
Enfoque de última ocurrencia: el enfoque optimizado en tiempo lineal y espacio constante se analiza en el Conjunto 1 de este artículo . Aquí, estamos discutiendo el enfoque de programación dinámica.
Enfoque de programación dinámica: este problema se puede resolver utilizando programación dinámica al observar los siguientes hechos, que si se requiere la eliminación de K para hacer que la string se ordene hasta el i -ésimo índice y
- Caso 1: S[i+1] = 1 , entonces el número mínimo de eliminaciones requeridas para ordenar la string hasta (i+1) el índice también será K , ya que agregar 1 a una string ordenada mantendrá la string ordenada, por lo que no se requieren más eliminaciones.
- Caso 2: S[i + 1] = 0 , entonces tenemos dos formas de ordenar strings hasta (i+1) el índice que son
- elimine todos los 1 antes del índice (i+1) o
- eliminar actual 0 .
El número mínimo de eliminaciones para que la string sea válida hasta el índice (i+1)th será mínimo de (números de 1 antes del índice (i+1)th, K+1).
Siga los pasos a continuación para resolver el problema:
- Inicialice las variables count1 como 0 y N es la longitud de la string s .
- Inicialice el vector dp[n+1] con valores 0.
- Itere sobre el rango [0, n) usando la variable i y realice las siguientes tareas:
- Si s[i] es igual a 0, establezca dp[i+1] como el mínimo de count1 o 1 + dp[i].
- De lo contrario, establezca dp[i+1] como dp[i] y aumente el valor de count1 en 1.
- Después de realizar los pasos anteriores, imprima el valor de dp[n] como respuesta.
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 find the minimum number
// of deletions to make
// the string sorted
int minDeletions(string s)
{
int n = s.size();
// dp[i+1] stores minimum number of
// deletion to make
// substring(0, i) valid
vector<int> dp(n + 1, 0);
int count1 = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '0') {
// Case 1: remove current 0
// Case 2: keep current 0
// then delete all 1 before it
dp[i + 1] = min(count1,
1 + dp[i]);
}
else {
// Appending 1 is always valid
// if substring(0, i) is sorted
dp[i + 1] = dp[i];
count1++;
}
}
return dp[n];
}
// Driver Code
int main()
{
string s = "00101101";
cout << minDeletions(s);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class GFG
{
// Function to find the minimum number
// of deletions to make
// the string sorted
static int minDeletions(String s)
{
int n = s.length();
// dp[i+1] stores minimum number of
// deletion to make
// substring(0, i) valid
int []dp = new int[n + 1];
for(int i = 0; i < n + 1; i++) {
dp[i] = 0;
}
int count1 = 0;
for (int i = 0; i < n; i++) {
if (s.charAt(i) == '0') {
// Case 1: remove current 0
// Case 2: keep current 0
// then delete all 1 before it
dp[i + 1] = Math.min(count1,
1 + dp[i]);
}
else {
// Appending 1 is always valid
// if substring(0, i) is sorted
dp[i + 1] = dp[i];
count1++;
}
}
return dp[n];
}
// Driver Code
public static void main(String args[])
{
String s = "00101101";
System.out.println(minDeletions(s));
}
}
// This code is contributed by Samim Hossain Mondal.
Python3
# Python code for the above approach # Function to find the minimum number # of deletions to make # the string sorted def minDeletions(s): n = len(s) # dp[i+1] stores minimum number of # deletion to make # substring(0, i) valid dp = [0] * (n + 1) count1 = 0 for i in range(n): if (s[i] == '0'): # Case 1: remove current 0 # Case 2: keep current 0 # then delete all 1 before it dp[i + 1] = min(count1, 1 + dp[i]) else: # Appending 1 is always valid # if substring(0, i) is sorted dp[i + 1] = dp[i] count1 += 1 return dp[n] # Driver Code s = "00101101" print(minDeletions(s)) # This code is contributed by Saurabh Jaiswal
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to find the minimum number
// of deletions to make
// the string sorted
static int minDeletions(string s)
{
int n = s.Length;
// dp[i+1] stores minimum number of
// deletion to make
// substring(0, i) valid
int[] dp = new int[n + 1];
for (int i = 0; i < n + 1; i++)
{
dp[i] = 0;
}
int count1 = 0;
for (int i = 0; i < n; i++)
{
if (s[i] == '0')
{
// Case 1: remove current 0
// Case 2: keep current 0
// then delete all 1 before it
dp[i + 1] = Math.Min(count1,
1 + dp[i]);
}
else
{
// Appending 1 is always valid
// if substring(0, i) is sorted
dp[i + 1] = dp[i];
count1++;
}
}
return dp[n];
}
// Driver Code
public static void Main()
{
string s = "00101101";
Console.Write(minDeletions(s));
}
}
// This code is contributed by Saurabh Jaiswal
Javascript
<script>
// JavaScript code for the above approach
// Function to find the minimum number
// of deletions to make
// the string sorted
function minDeletions(s) {
let n = s.length;
// dp[i+1] stores minimum number of
// deletion to make
// substring(0, i) valid
let dp = new Array(n + 1).fill(0);
let count1 = 0;
for (let i = 0; i < n; i++) {
if (s[i] == '0') {
// Case 1: remove current 0
// Case 2: keep current 0
// then delete all 1 before it
dp[i + 1] = Math.min(count1,
1 + dp[i]);
}
else {
// Appending 1 is always valid
// if substring(0, i) is sorted
dp[i + 1] = dp[i];
count1++;
}
}
return dp[n];
}
// Driver Code
let s = "00101101";
document.write(minDeletions(s));
// This code is contributed by Potta Lokesh
</script>
Producción
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por sachinjain74754 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA