Subsecuencia más larga con 0 y 1 iguales y todos los 0 antes que todos los 1

Posted on by Rudeus Greyrat

Dada una string binaria S , la tarea es encontrar la subsecuencia más larga que tenga el mismo número de 0 y 1 y que todos los 0 estén presentes antes que todos los 1.

Ejemplos:

Entrada: S = “0011001111”
Salida: 8
Explicación: Al eliminar los caracteres 3 y 4, la string se convierte en 00001111. 
Esta es la subsecuencia más larga posible siguiendo las condiciones dadas.

Entrada: S = “11001”
Salida: 2
Explicación: La subsecuencia más larga posible que satisface las condiciones es “01”

Entrada: S = “111100”
Salida: 0
Explicación : No existe tal subsecuencia que satisfaga las condiciones.

 

 Planteamiento: El problema se puede resolver a partir de la siguiente idea:

Para cada índice, debemos elegir el número máximo de 0 desde el principio y el número máximo de 1 desde el final. Esto maximizará la longitud de la subsecuencia requerida.

Con base en la idea anterior, necesitamos hacer lo siguiente: 

  • Para cada índice, calcule el número total de 0 desde el principio y el número total de 1 desde el final. 
  • Si los 1 comienzan desde el i -ésimo índice, entonces la longitud total de la subsecuencia será = 2 * min ( 0 desde el inicio hasta i, 1 desde el final hasta i) . 
  • El máximo de esto para todos los índices es la respuesta.

Siga los pasos mencionados a continuación para implementar la idea:

  • Cree dos arrays (por ejemplo , pre[] y post[] ) para almacenar el recuento de 0 desde el principio y el recuento de 1 desde el final.
  • Iterar de i = 0 a N-1 :
    • Si S[i] es 0, incremente el conteo de 0 y guárdelo en pre[i] .
  • Iterar de i = N-1 a 0 :
    • Si S[i] es 1, incremente el conteo 1s desde el final y guárdelo en post[i] .
  • Iterar las arrays de i = 0 a N-1 :
    • Calcule la longitud de la subsecuencia si este índice es el punto de ruptura entre 1 y 0.
    • El máximo entre estas subsecuencias es la longitud requerida de la subsecuencia.

A continuación se muestra la implementación del enfoque anterior.

C++

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the length
// of the longest subsequence
int longestGoodString(string s)
{
    // Size of the string
    int n = s.size();
 
    // The pre is used to store the count of 0s
    // encountered from start to i index
 
    // The post is used to store the count of 1s
    // encountered from n-1 index to i index
    vector<int> pre(n, 0), post(n, 0);
 
    if (s[0] == '0')
        pre[0] = 1;
 
    // Loop to calculate the value of pre[i]
    for (int i = 1; i < n; i++) {
        if (s[i] == '0')
            pre[i] = pre[i - 1] + 1;
        else
            pre[i] = pre[i - 1];
    }
 
    if (s[n - 1] == '1')
        post[n - 1] = 1;
 
    // Loop to calculate the value of post[i]
    for (int i = n - 2; i >= 0; i--) {
        if (s[i] == '1')
            post[i] = 1 + post[i + 1];
        else
            post[i] = post[i + 1];
    }
 
    // Picking up the maximum possible length
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, 2 * min(pre[i], post[i]));
    }
 
    // Return the maximum length as answer
    return ans;
}
 
// Driver code
int main()
{
    string S = "0011001111";
 
    // Function call
    cout << longestGoodString(S);
    return 0;
}

Java

// Java code to implement the approach
import java.io.*;
 
class GFG
{
 
  // Function to find the length
  // of the longest subsequence
  public static int longestGoodString(String s)
  {
    // Size of the string
    int n = s.length();
 
    // The pre is used to store the count of 0s
    // encountered from start to i index
 
    // The post is used to store the count of 1s
    // encountered from n-1 index to i index
    int pre[] = new int[n];
    int post[] = new int[n];
 
    if (s.charAt(0) == '0')
      pre[0] = 1;
 
    // Loop to calculate the value of pre[i]
    for (int i = 1; i < n; i++) {
      if (s.charAt(i) == '0')
        pre[i] = pre[i - 1] + 1;
      else
        pre[i] = pre[i - 1];
    }
 
    if (s.charAt(n - 1) == '1')
      post[n - 1] = 1;
 
    // Loop to calculate the value of post[i]
    for (int i = n - 2; i >= 0; i--) {
      if (s.charAt(i) == '1')
        post[i] = 1 + post[i + 1];
      else
        post[i] = post[i + 1];
    }
 
    // Picking up the maximum possible length
    int ans = 0;
    for (int i = 0; i < n; i++) {
      ans = Math.max(ans,
                     2 * Math.min(pre[i], post[i]));
    }
 
    // Return the maximum length as answer
    return ans;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    String S = "0011001111";
 
    // Function call
    System.out.print(longestGoodString(S));
  }
}
 
// This code is contributed by Rohit Pradhan

Python3

# Python3 code to implement the approach
# Function to find the length
# of the longest subsequence
def longestGoodString(s):
    # Size of the string
    n =  len(s)
 
    # The pre is used to store the count of 0s
    # encountered from start to i index
 
    # The post is used to store the count of 1s
    # encountered from n-1 index to i index
    pre = []
    post=[]
       
    for i in range(n):
      pre.append(0)
      post.append(0)
 
    if (s[0] is '0'):
        pre[0] = 1
 
    # Loop to calculate the value of pre[i]
    for i in range(1,n):
        if (s[i] is '0'):
            pre[i] = pre[i - 1] + 1
        else:
            pre[i] = pre[i - 1]
 
    if (s[n - 1] is '1'):
        post[n - 1] = 1
 
    # Loop to calculate the value of post[i]
    for i in range(n-2,-1,-1):
        if (s[i] is '1'):
            post[i] = 1 + post[i + 1]
        else:
            post[i] = post[i + 1]
 
    # Picking up the maximum possible length
    ans = 0
    for i in range(n):
        ans = max(ans, 2 * min(pre[i], post[i]))
 
    # Return the maximum length as answer
    return ans
 
# Driver code
S = "0011001111"
 
# Function call
print(longestGoodString(S))
 
# This code is contributed by akashish__

C#

// C# code to implement the approach
using System;
public class GFG
{
 
  // Function to find the length
  // of the longest subsequence
  public static int longestGoodString(String s)
  {
    // Size of the string
    int n = s.Length;
 
    // The pre is used to store the count of 0s
    // encountered from start to i index
 
    // The post is used to store the count of 1s
    // encountered from n-1 index to i index
    int []pre = new int[n];
    int []post = new int[n];
 
    if (s[0] == '0')
      pre[0] = 1;
 
    // Loop to calculate the value of pre[i]
    for (int i = 1; i < n; i++) {
      if (s[i] == '0')
        pre[i] = pre[i - 1] + 1;
      else
        pre[i] = pre[i - 1];
    }
 
    if (s[n - 1] == '1')
      post[n - 1] = 1;
 
    // Loop to calculate the value of post[i]
    for (int i = n - 2; i >= 0; i--) {
      if (s[i] == '1')
        post[i] = 1 + post[i + 1];
      else
        post[i] = post[i + 1];
    }
 
    // Picking up the maximum possible length
    int ans = 0;
    for (int i = 0; i < n; i++) {
      ans = Math.Max(ans,
                     2 * Math.Min(pre[i], post[i]));
    }
 
    // Return the maximum length as answer
    return ans;
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
    string S = "0011001111";
 
    // Function call
    Console.WriteLine(longestGoodString(S));
  }
}
 
// This code is contributed by AnkThon

Javascript

<script>
        // JavaScript code to implement the approach
 
        // Function to find the length
        // of the longest subsequence
        const longestGoodString = (s) => {
            // Size of the string
            let n = s.length;
 
            // The pre is used to store the count of 0s
            // encountered from start to i index
 
            // The post is used to store the count of 1s
            // encountered from n-1 index to i index
            let pre = new Array(n).fill(0), post = new Array(n).fill(0);
 
            if (s[0] == '0')
                pre[0] = 1;
 
            // Loop to calculate the value of pre[i]
            for (let i = 1; i < n; i++) {
                if (s[i] == '0')
                    pre[i] = pre[i - 1] + 1;
                else
                    pre[i] = pre[i - 1];
            }
 
            if (s[n - 1] == '1')
                post[n - 1] = 1;
 
            // Loop to calculate the value of post[i]
            for (let i = n - 2; i >= 0; i--) {
                if (s[i] == '1')
                    post[i] = 1 + post[i + 1];
                else
                    post[i] = post[i + 1];
            }
 
            // Picking up the maximum possible length
            let ans = 0;
            for (let i = 0; i < n; i++) {
                ans = Math.max(ans, 2 * Math.min(pre[i], post[i]));
            }
 
            // Return the maximum length as answer
            return ans;
        }
 
        // Driver code
 
        let S = "0011001111";
 
        // Function call
        document.write(longestGoodString(S));
 
        // This code is contributed by rakeshsahni
 
    </script>
Producción

8

Complejidad de tiempo: O(N) donde N es la longitud de la string
Espacio auxiliar: O(N) 

Publicación traducida automáticamente

Artículo escrito por abhilashreddy1676 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *