La substring binaria equilibrada más larga con el mismo recuento de 1 y 0

Posted on by Rudeus Greyrat

Dada una string binaria str[] de tamaño N . La tarea es encontrar la substring balanceada más larga . Una substring está balanceada si contiene un número igual de 0 y 1 .

Ejemplos:  

Entrada: str = “110101010”
Salida: 10101010
Explicación: La substring formada contiene el mismo recuento de 1 y 0, es decir, el recuento de 1 y 0 es igual a 4.

Entrada: str = “0000”
Salida: -1

 

Enfoque ingenuo: una solución simple es usar dos bucles anidados para generar cada substring . Y un tercer ciclo para contar un número de 0 y 1 en la substring actual . Luego imprima la substring más larga entre ellos. 
Complejidad de tiempo: O(N^3)
Espacio auxiliar: O(1)

Solución eficiente: con la ayuda del cálculo previo, almacene la diferencia entre el recuento de 0 y el recuento de 1 desde el inicio hasta el índice actual. Esta diferencia se puede usar para determinar la substring más larga con 0 y 1 iguales , como la distancia más larga entre cualquier valor duplicado en la array de diferencia. Utilice un hash basado en mapas para realizar cálculos previos. Siga los pasos a continuación para resolver el problema:

  • Inicialice el mapa <int, int> m[].
  • Establezca el valor de m[0] como -1.
  • Inicialice las variables count_0, count_1, res, start y end .
  • Recorra la string str[] usando la variable i y realice las siguientes tareas:
    • Lleve un registro de los recuentos de 1 y 0 como count_1 y count_0 respectivamente.
    • Vea si la diferencia actual entre count_1 y count_0 ya está en el mapa m[] o no. En caso afirmativo, realice las siguientes tareas:
      • La substring de la aparición anterior y el índice actual tiene el mismo número de 0 y 1 .
      • Si la longitud de la substring encontrada actual es mayor que res , establezca la substring encontrada como la respuesta hasta el momento.
    • Si aparece por primera vez, almacene la diferencia actual y el índice actual en el mapa, es decir, m[count_1 – count_0] es igual a i .
  • Si count_0 y count_1 son ambos 0, imprima -1.
  • De lo contrario, imprima la substring de principio a fin.

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

C++

// C++ for finding length
// of longest balanced substring
#include <bits/stdc++.h>
using namespace std;
 
// Returns length of the longest substring
// with equal number of zeros and ones.
string stringLen(string str)
{
 
    // Create a map to store differences
    // between counts of 1s and 0s.
    map<int, int> m;
 
    // Initially difference is 0.
    m[0] = -1;
 
    int count_0 = 0, count_1 = 0;
    int start, end, res = 0;
    for (int i = 0; i < str.size(); i++) {
 
        // Keeping track of counts of
        // 0s and 1s.
        if (str[i] == '0')
            count_0++;
        else
            count_1++;
 
        // If difference between current counts
        // already exists, then substring between
        // previous and current index has same
        // no. of 0s and 1s. Update result if this
        // substring is more than current result.
        if (m.find(count_1 - count_0) != m.end()) {
 
            if ((i - m[count_1 - count_0]) > res) {
 
                start = m.find(
                             count_1 - count_0)
                            ->second;
                end = i;
                res = end - start;
            }
        }
 
        // If current difference
        // is seen first time.
        else
            m[count_1 - count_0] = i;
    }
 
    if (count_0 == 0 || count_1 == 0)
        return "-1";
 
    // Return the substring
    // between found indices
    return str.substr(start + 1, end + 1);
}
 
// Driver Code
int main()
{
    string str = "110101010";
    cout << stringLen(str);
    return 0;
}

Java

// Java code for the above approach
import java.io.*;
class GFG
{
 
  // Returns length of the longest substring
  // with equal number of zeros and ones.
  static String stringLen(String str)
  {
 
    // Create a map to store differences
    // between counts of 1s and 0s.
    int [] m = new int[100000];
 
    // Initially difference is 0.
    m[0] = -1;
 
    int count_0 = 0; int count_1 = 0;
    int start = 0; int end = 0; int res = 0;
    for (int i = 0; i < str.length(); i++) {
 
      // Keeping track of counts of
      // 0s and 1s.
      if (str.charAt(i) == '0')
        count_0++;
      else
        count_1++;
 
      // If difference between current counts
      // already exists, then substring between
      // previous and current index has same
      // no. of 0s and 1s. Update result if this
      // substring is more than current result.
      if (m[count_1 - count_0]!= 0) {
 
        if ((i - m[count_1 - count_0]) > res) {
 
          start = m[count_1 - count_0];
 
          end = i;
          res = end - start;
        }
      }
 
      // If current difference
      // is seen first time.
      else
        m[count_1 - count_0] = i;
    }
 
    if (count_0 == 0 || count_1 == 0)
      return "-1";
 
    // Return the substring
    // between found indices
    return str.substring(start , end + 2);
  }
 
  // Driver Code
  public static void main (String[] args)
  {
    String str = "110101010";
 
    System.out.println(stringLen(str));
  }
}
 
// This code is contributed by Potta Lokesh

Python3

# Python for finding length
# of longest balanced substring
 
# Returns length of the longest substring
# with equal number of zeros and ones.
def stringLen (str) :
 
    # Create a map to store differences
    # between counts of 1s and 0s.
    m = {}
 
    # Initially difference is 0.
    m[0] = -1
 
    count_0 = 0
    count_1 = 0
    res = 0
    for i in range(len(str)):
 
        # Keeping track of counts of
        # 0s and 1s.
        if (str[i] == '0'):
            count_0 += 1
        else:
            count_1 += 1
 
        # If difference between current counts
        # already exists, then substring between
        # previous and current index has same
        # no. of 0s and 1s. Update result if this
        # substring is more than current result.
        if ((count_1 - count_0) in m):
 
            if ((i - m[count_1 - count_0]) > res):
 
                start = m[(count_1 - count_0)]
                end = i
                res = end - start
             
        # If current difference
        # is seen first time.
        else:
            m[count_1 - count_0] = i
     
    if (count_0 == 0 or count_1 == 0):
        return "-1"
 
    # Return the substring
    # between found indices
    return str[start + 1 : start + 1 + end + 1]
 
# Driver Code
str = "110101010"
print(stringLen(str))
 
# This code is contributed by Saurabh Jaiswal

C#

// C# code for the above approach
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG
{
 
  // Returns length of the longest substring
  // with equal number of zeros and ones.
  static string stringLen(string str)
  {
 
    // Create a map to store differences
    // between counts of 1s and 0s.
    int []m = new int[100000];
 
    // Initially difference is 0.
    m[0] = -1;
 
    int count_0 = 0; int count_1 = 0;
    int start = 0; int end = 0; int res = 0;
    for (int i = 0; i < str.Length; i++) {
 
      // Keeping track of counts of
      // 0s and 1s.
      if (str[i] == '0')
        count_0++;
      else
        count_1++;
 
      // If difference between current counts
      // already exists, then substring between
      // previous and current index has same
      // no. of 0s and 1s. Update result if this
      // substring is more than current result.
      if (m[count_1 - count_0]!= 0) {
 
        if ((i - m[count_1 - count_0]) > res) {
 
          start = m[count_1 - count_0];
 
          end = i;
          res = end - start;
        }
      }
 
      // If current difference
      // is seen first time.
      else
        m[count_1 - count_0] = i;
    }
 
    if (count_0 == 0 || count_1 == 0)
      return "-1";
 
    // Return the substring
    // between found indices
    return str.Substring(start, end - start + 2);
  }
 
  // Driver Code
  public static void Main ()
  {
    string str = "110101010";
 
    Console.Write(stringLen(str));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
    // JavaScript for finding length
    // of longest balanced substring
 
    // Returns length of the longest substring
    // with equal number of zeros and ones.
    const stringLen = (str) => {
 
        // Create a map to store differences
        // between counts of 1s and 0s.
        let m = {};
 
        // Initially difference is 0.
        m[0] = -1;
 
        let count_0 = 0, count_1 = 0;
        let start, end, res = 0;
        for (let i = 0; i < str.length; i++) {
 
            // Keeping track of counts of
            // 0s and 1s.
            if (str[i] == '0')
                count_0++;
            else
                count_1++;
 
            // If difference between current counts
            // already exists, then substring between
            // previous and current index has same
            // no. of 0s and 1s. Update result if this
            // substring is more than current result.
            if ((count_1 - count_0) in m) {
 
                if ((i - m[count_1 - count_0]) > res) {
 
                    start = m[(count_1 - count_0)];
                    end = i;
                    res = end - start;
                }
            }
 
            // If current difference
            // is seen first time.
            else
                m[count_1 - count_0] = i;
        }
 
        if (count_0 == 0 || count_1 == 0)
            return "-1";
 
        // Return the substring
        // between found indices
        return str.substring(start + 1, start + 1 + end + 1);
    }
 
    // Driver Code
    let str = "110101010";
    document.write(stringLen(str));
 
    // This code is contributed by rakeshsahni
</script>
Producción

10101010

Complejidad temporal: O(N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por Code_r 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 *