Dada una string binaria s , la tarea es encontrar la longitud de la subsecuencia más larga que se puede dividir en tres substrings, de modo que la primera y la tercera substrings estén vacías o llenas con 1 y la substring en el medio esté vacía o llena con 0.
Ejemplos:
Entrada: s = “1001”
Salida: 4
Explicación:
La string completa se puede dividir en las tres partes deseadas: “1”, “00”, “1”.Entrada: s = “010”
Salida: 2
Explicación:
Las subsecuencias “00”, “01” y “10” se pueden dividir en tres partes deseadas {“”, “00”, “”}, {“”, “0 ”, “1”} y {“1”, “0”, “”}
Enfoque:
Para resolver el problema, debemos seguir los pasos que se detallan a continuación:
- En primer lugar, calcule previamente y almacene en arrays de prefijos , las ocurrencias de ‘1’ y ‘0’ respectivamente.
- Inicialice dos enteros i y j , donde i será el punto de partición entre la primera y la segunda string y j será el punto de partición entre la segunda y la tercera string.
- Iterar sobre todos los valores posibles de i & j (0 <= i < j <=n) y encontrar la longitud máxima posible de la subsecuencia que satisfaga la condición dada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to find the
// longest subsequence possible
// that starts and ends with 1
// and filled with 0 in the middle
#include <bits/stdc++.h>
using namespace std;
int longestSubseq(string s, int length)
{
// Prefix array to store the
// occurrences of '1' and '0'
int ones[length + 1], zeroes[length + 1];
// Initialise prefix arrays with 0
memset(ones, 0, sizeof(ones));
memset(zeroes, 0, sizeof(zeroes));
// Iterate over the length of the string
for (int i = 0; i < length; i++) {
// If current character is '1'
if (s[i] == '1') {
ones[i + 1] = ones[i] + 1;
zeroes[i + 1] = zeroes[i];
}
// If current character is '0'
else {
zeroes[i + 1] = zeroes[i] + 1;
ones[i + 1] = ones[i];
}
}
int answer = INT_MIN;
int x = 0;
for (int i = 0; i <= length; i++) {
for (int j = i; j <= length; j++) {
// Add '1' available for
// the first string
x += ones[i];
// Add '0' available for
// the second string
x += (zeroes[j] - zeroes[i]);
// Add '1' available for
// the third string
x += (ones[length] - ones[j]);
// Update answer
answer = max(answer, x);
x = 0;
}
}
// Print the final result
cout << answer << endl;
}
// Driver Code
int main()
{
string s = "10010010111100101";
int length = s.length();
longestSubseq(s, length);
return 0;
}
Java
// Java program to find the
// longest subsequence possible
// that starts and ends with 1
// and filled with 0 in the middle
import java.io.*;
class GFG{
static void longestSubseq(String s,
int length)
{
// Prefix array to store the
// occurrences of '1' and '0'
int[] ones = new int[length + 1];
int[] zeroes = new int[length + 1];
// Iterate over the length of
// the string
for(int i = 0; i < length; i++)
{
// If current character is '1'
if (s.charAt(i) == '1')
{
ones[i + 1] = ones[i] + 1;
zeroes[i + 1] = zeroes[i];
}
// If current character is '0'
else
{
zeroes[i + 1] = zeroes[i] + 1;
ones[i + 1] = ones[i];
}
}
int answer = Integer.MIN_VALUE;
int x = 0;
for(int i = 0; i <= length; i++)
{
for(int j = i; j <= length; j++)
{
// Add '1' available for
// the first string
x += ones[i];
// Add '0' available for
// the second string
x += (zeroes[j] - zeroes[i]);
// Add '1' available for
// the third string
x += (ones[length] - ones[j]);
// Update answer
answer = Math.max(answer, x);
x = 0;
}
}
// Print the final result
System.out.println(answer);
}
// Driver code
public static void main(String[] args)
{
String s = "10010010111100101";
int length = s.length();
longestSubseq(s, length);
}
}
// This code is contributed by offbeat
Python3
# Python3 program to find the # longest subsequence possible # that starts and ends with 1 # and filled with 0 in the middle import sys def longestSubseq(s, length): # Prefix array to store the # occurrences of '1' and '0' # Initialise prefix arrays with 0 ones = [0 for i in range(length + 1)] zeroes = [0 for i in range(length + 1)] # Iterate over the length of the string for i in range(length): # If current character is '1' if(s[i] == '1'): ones[i + 1] = ones[i] + 1 zeroes[i + 1] = zeroes[i] # If current character is '0' else: zeroes[i + 1] = zeroes[i] + 1 ones[i + 1] = ones[i] answer = -sys.maxsize - 1 x = 0 for i in range(length + 1): for j in range(i, length + 1): # Add '1' available for # the first string x += ones[i] # Add '0' available for # the second string x += (zeroes[j] - zeroes[i]) # Add '1' available for # the third string x += (ones[length] - ones[j]) # Update answer answer = max(answer, x) x = 0 # Print the final result print(answer) # Driver Code S = "10010010111100101" length = len(S) longestSubseq(S, length) # This code is contributed by avanitrachhadiya2155
C#
// C# program to find the
// longest subsequence possible
// that starts and ends with 1
// and filled with 0 in the middle
using System;
class GFG{
static void longestSubseq(String s,
int length)
{
// Prefix array to store the
// occurrences of '1' and '0'
int[] ones = new int[length + 1];
int[] zeroes = new int[length + 1];
// Iterate over the length of
// the string
for(int i = 0; i < length; i++)
{
// If current character is '1'
if (s[i] == '1')
{
ones[i + 1] = ones[i] + 1;
zeroes[i + 1] = zeroes[i];
}
// If current character is '0'
else
{
zeroes[i + 1] = zeroes[i] + 1;
ones[i + 1] = ones[i];
}
}
int answer = int.MinValue;
int x = 0;
for(int i = 0; i <= length; i++)
{
for(int j = i; j <= length; j++)
{
// Add '1' available for
// the first string
x += ones[i];
// Add '0' available for
// the second string
x += (zeroes[j] - zeroes[i]);
// Add '1' available for
// the third string
x += (ones[length] - ones[j]);
// Update answer
answer = Math.Max(answer, x);
x = 0;
}
}
// Print the readonly result
Console.WriteLine(answer);
}
// Driver code
public static void Main(String[] args)
{
String s = "10010010111100101";
int length = s.Length;
longestSubseq(s, length);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript program to find the
// longest subsequence possible
// that starts and ends with 1
// and filled with 0 in the middle
function longestSubseq(s, len) {
// Prefix array to store the
// occurrences of '1' and '0'
var ones = new Array(len + 1).fill(0);
var zeroes = new Array(len + 1).fill(0);
// Iterate over the length of
// the string
for (var i = 0; i < len; i++) {
// If current character is '1'
if (s[i] === "1") {
ones[i + 1] = ones[i] + 1;
zeroes[i + 1] = zeroes[i];
}
// If current character is '0'
else {
zeroes[i + 1] = zeroes[i] + 1;
ones[i + 1] = ones[i];
}
}
var answer = -2147483648;
var x = 0;
for (var i = 0; i <= len; i++) {
for (var j = i; j <= len; j++) {
// Add '1' available for
// the first string
x += ones[i];
// Add '0' available for
// the second string
x += zeroes[j] - zeroes[i];
// Add '1' available for
// the third string
x += ones[len] - ones[j];
// Update answer
answer = Math.max(answer, x);
x = 0;
}
}
// Print the readonly result
document.write(answer);
}
// Driver code
var s = "10010010111100101";
var len = s.length;
longestSubseq(s, len);
</script>
Producción:
12
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Adityasharma15 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA