Dada una string binaria, encuentre la subsecuencia más larga de la forma (0)*(1)*(0)* en ella. Básicamente, necesitamos dividir la string en 3 strings que no se superpongan (estas strings pueden estar vacías) sin cambiar el orden de las letras. La primera y la tercera string se componen de solo 0 y la segunda string se compone de solo 1. Estas strings se pueden crear eliminando algunos caracteres de la string original.
¿Cuál es el tamaño máximo de string que podemos obtener?
Ejemplos:
Input : 000011100000 Output : 12 Explanation : First part from 1 to 4. Second part 5 to 7. Third part from 8 to 12 Input : 100001100 Output : 8 Explanation : Delete the first letter. First part from 2 to 4. Second part from 5 to 6. Last part from 7. Input : 00000 Output : 5 Explanation : Special Case of Only 0 Input : 111111 Output : 6 Explanation : Special Case of Only 1 Input : 0000001111011011110000 Output : 20 Explanation : Second part is from 7 to 18. Remove all the 0 between indices 7 to 18.
Una solución simple es generar todas las subsecuencias de una secuencia dada . Para cada subsecuencia, verifique si está en la forma dada. En caso afirmativo, compárelo con el resultado hasta el momento y actualice el resultado si es necesario.
Este problema se puede resolver de manera eficiente mediante el cálculo previo debajo de las arrays en tiempo O (n ^ 2) .
Sea pre_count_0[i] el conteo de la letra 0 en el prefijo de la string hasta el índice i.
Sea pre_count_1[i] el conteo de la letra 1 en el prefijo de la string hasta la longitud i.
Sea post_count_0[i] el conteo de la letra 0 en la string de sufijos desde el índice i hasta el índice n (aquí n es el tamaño de la string).
Ahora arreglamos dos dos posiciones i y j, 1 <=i <= j <=n. Eliminaremos todos los 0 de la substring que comienza en el índice i y termina en el índice j. Por lo tanto, esto hace que la segunda substring sea solo 1. En el prefijo antes del índice i y en el sufijo después del índice j, eliminaremos todos los 1 y, por lo tanto, formará la primera y la tercera parte de la string.
entonces la longitud máxima de string alcanzable es max de
pre_count_0[i-1] + (pre_count_1[j]-pre_count_1[i-1]) + pre_count_1[j+1]
Casos especiales: cuando String se compone solo de 0 o 1, ans es n donde n es la longitud de la string.
Implementación:
C++
// CPP program to find longest subsequence
// of the form 0*1*0* in a binary string
#include <bits/stdc++.h>
using namespace std;
// Returns length of the longest subsequence
// of the form 0*1*0*
int longestSubseq(string s)
{
int n = s.length();
// Precomputing values in three arrays
// pre_count_0[i] is going to store count
// of 0s in prefix str[0..i-1]
// pre_count_1[i] is going to store count
// of 1s in prefix str[0..i-1]
// post_count_0[i] is going to store count
// of 0s in suffix str[i-1..n-1]
int pre_count_0[n + 2];
int pre_count_1[n + 1];
int post_count_0[n + 1];
pre_count_0[0] = 0;
post_count_0[n + 1] = 0;
pre_count_1[0] = 0;
for (int j = 1; j <= n; j++)
{
pre_count_0[j] = pre_count_0[j - 1];
pre_count_1[j] = pre_count_1[j - 1];
post_count_0[n - j + 1] = post_count_0[n - j + 2];
if (s[j - 1] == '0')
pre_count_0[j]++;
else
pre_count_1[j]++;
if (s[n - j] == '0')
post_count_0[n - j + 1]++;
}
// string is made up of all 0s or all 1s
if (pre_count_0[n] == n ||
pre_count_0[n] == 0)
return n;
// Compute result using precomputed values
int ans = 0;
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++)
ans = max(pre_count_0[i - 1]
+ pre_count_1[j]
- pre_count_1[i - 1]
+ post_count_0[j + 1],
ans);
return ans;
}
// driver program
int main()
{
string s = "000011100000";
cout << longestSubseq(s);
return 0;
}
Java
// Java program to find longest subsequence
// of the form 0*1*0* in a binary string
class GFG
{
// Returns length of the longest subsequence
// of the form 0*1*0*
public static int longestSubseq(String s)
{
int n = s.length();
// Precomputing values in three arrays
// pre_count_0[i] is going to store count
// of 0s in prefix str[0..i-1]
// pre_count_1[i] is going to store count
// of 1s in prefix str[0..i-1]
// post_count_0[i] is going to store count
// of 0s in suffix str[i-1..n-1]
int[] pre_count_0 = new int[n + 2];
int[] pre_count_1 = new int[n + 1];
int[] post_count_0 = new int[n + 2];
pre_count_0[0] = 0;
post_count_0[n + 1] = 0;
pre_count_1[0] = 0;
for (int j = 1; j <= n; j++)
{
pre_count_0[j] = pre_count_0[j - 1];
pre_count_1[j] = pre_count_1[j - 1];
post_count_0[n - j + 1] = post_count_0[n - j + 2];
if (s.charAt(j - 1) == '0')
pre_count_0[j]++;
else
pre_count_1[j]++;
if (s.charAt(n - j) == '0')
post_count_0[n - j + 1]++;
}
// string is made up of all 0s or all 1s
if (pre_count_0[n] == n ||
pre_count_0[n] == 0)
return n;
// Compute result using precomputed values
int ans = 0;
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++)
ans = Math.max(pre_count_0[i - 1] +
pre_count_1[j] -
pre_count_1[i - 1] +
post_count_0[j + 1], ans);
return ans;
}
// Driver code
public static void main(String[] args)
{
String s = "000011100000";
System.out.println(longestSubseq(s));
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python 3 program to find longest subsequence # of the form 0*1*0* in a binary string # Returns length of the longest subsequence # of the form 0*1*0* def longestSubseq(s): n = len(s) # Precomputing values in three arrays # pre_count_0[i] is going to store count # of 0s in prefix str[0..i-1] # pre_count_1[i] is going to store count # of 1s in prefix str[0..i-1] # post_count_0[i] is going to store count # of 0s in suffix str[i-1..n-1] pre_count_0 = [0 for i in range(n + 2)] pre_count_1 = [0 for i in range(n + 1)] post_count_0 = [0 for i in range(n + 2)] pre_count_0[0] = 0 post_count_0[n + 1] = 0 pre_count_1[0] = 0 for j in range(1, n + 1): pre_count_0[j] = pre_count_0[j - 1] pre_count_1[j] = pre_count_1[j - 1] post_count_0[n - j + 1] = post_count_0[n - j + 2] if (s[j - 1] == '0'): pre_count_0[j] += 1 else: pre_count_1[j] += 1 if (s[n - j] == '0'): post_count_0[n - j + 1] += 1 # string is made up of all 0s or all 1s if (pre_count_0[n] == n or pre_count_0[n] == 0): return n # Compute result using precomputed values ans = 0 for i in range(1, n + 1): for j in range(i, n + 1, 1): ans = max(pre_count_0[i - 1] + pre_count_1[j] - pre_count_1[i - 1] + post_count_0[j + 1], ans) return ans # Driver Code if __name__ == '__main__': s = "000011100000" print(longestSubseq(s)) # This code is contributed by # Surendra_Gangwar
C#
// C# program to find longest subsequence
// of the form 0*1*0* in a binary string
using System;
class GFG
{
// Returns length of the longest subsequence
// of the form 0*1*0*
public static int longestSubseq(String s)
{
int n = s.Length;
// Precomputing values in three arrays
// pre_count_0[i] is going to store count
// of 0s in prefix str[0..i-1]
// pre_count_1[i] is going to store count
// of 1s in prefix str[0..i-1]
// post_count_0[i] is going to store count
// of 0s in suffix str[i-1..n-1]
int[] pre_count_0 = new int[n + 2];
int[] pre_count_1 = new int[n + 1];
int[] post_count_0 = new int[n + 2];
pre_count_0[0] = 0;
post_count_0[n + 1] = 0;
pre_count_1[0] = 0;
for (int j = 1; j <= n; j++)
{
pre_count_0[j] = pre_count_0[j - 1];
pre_count_1[j] = pre_count_1[j - 1];
post_count_0[n - j + 1] = post_count_0[n - j + 2];
if (s[j - 1] == '0')
pre_count_0[j]++;
else
pre_count_1[j]++;
if (s[n - j] == '0')
post_count_0[n - j + 1]++;
}
// string is made up of all 0s or all 1s
if (pre_count_0[n] == n ||
pre_count_0[n] == 0)
return n;
// Compute result using precomputed values
int ans = 0;
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++)
ans = Math.Max(pre_count_0[i - 1] +
pre_count_1[j] -
pre_count_1[i - 1] +
post_count_0[j + 1], ans);
return ans;
}
// Driver code
public static void Main(String[] args)
{
String s = "000011100000";
Console.WriteLine(longestSubseq(s));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program to find longest subsequence
// of the form 0*1*0* in a binary string
// Returns length of the longest subsequence
// of the form 0*1*0*
function longestSubseq(s)
{
let n = s.length;
// Precomputing values in three arrays
// pre_count_0[i] is going to store count
// of 0s in prefix str[0..i-1]
// pre_count_1[i] is going to store count
// of 1s in prefix str[0..i-1]
// post_count_0[i] is going to store count
// of 0s in suffix str[i-1..n-1]
let pre_count_0 = new Array(n + 2);
let pre_count_1 = new Array(n + 1);
let post_count_0 = new Array(n + 2);
pre_count_0[0] = 0;
post_count_0[n + 1] = 0;
pre_count_1[0] = 0;
for(let j = 1; j <= n; j++)
{
pre_count_0[j] = pre_count_0[j - 1];
pre_count_1[j] = pre_count_1[j - 1];
post_count_0[n - j + 1] = post_count_0[n - j + 2];
if (s[j - 1] == '0')
pre_count_0[j]++;
else
pre_count_1[j]++;
if (s[n - j] == '0')
post_count_0[n - j + 1]++;
}
// String is made up of all 0s or all 1s
if (pre_count_0[n] == n ||
pre_count_0[n] == 0)
return n;
// Compute result using precomputed values
let ans = 0;
for(let i = 1; i <= n; i++)
for(let j = i; j <= n; j++)
ans = Math.max(pre_count_0[i - 1] +
pre_count_1[j] -
pre_count_1[i - 1] +
post_count_0[j + 1], ans);
return ans;
}
// Driver code
let s = "000011100000";
document.write(longestSubseq(s));
// This code is contributed by vaibhavrabadiya3
</script>
12
Este artículo es una contribución de nikhil ranjan 7 . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA