Distancia máxima entre 1 adyacentes en una string binaria dada

Dada una string binaria S que contiene N caracteres, la tarea es encontrar la distancia máxima entre dos 1 adyacentes . 

Ejemplos:

Entrada: S = “1010010”
Salida: 3
Explicación: Hay 2 conjuntos de 1 adyacentes en el índice dado en los índices {0, 2} y {2, 5}. 
El que tiene la distancia máxima entre ellos es {2, 5} con una distancia de 3 unidades.

Entrada: S = “100000”
Salida: -1
Explicación: No existe ningún conjunto de 1 adyacentes en la string dada.

Enfoque : El problema dado es un problema basado en la implementación. La idea es almacenar todos los índices de 1 en orden creciente en un vector . Por tanto, se puede observar que la respuesta requerida será el máximo de la diferencia de enteros consecutivos en el vector índice.

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

// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum
// distance between two adjacent
// 1's in a given binary string
int maxDist(string S)
{
    // Stores the required answer
    int maxLen = INT_MIN;
 
    // Vector to store indices
    vector<int> indices;
 
    // Loop to traverse string
    for (int i = 0; i < S.length(); i++) {
        if (S[i] == '1')
            indices.push_back(i);
    }
 
    // Loop to reverse the
    // index vector
    for (int i = 1; i < indices.size(); i++)
 
        // Update maximum distance
        maxLen = max(maxLen, indices[i] -
                     indices[i - 1]);
 
    // Return Answer
    return maxLen == INT_MIN ? -1 : maxLen;
}
 
// Driver Code
int main()
{
    string S = "1010010";
    cout << maxDist(S);
    return 0;
}

// Java program of the above approach
import java.io.*;
import java.util.*;
 
class GFG
{
 
  // Function to find the maximum
  // distance between two adjacent
  // 1's in a given binary String
  public static int maxDist(String S)
  {
     
    // Stores the required answer
    int maxLen = Integer.MIN_VALUE;
 
    // Vector to store indices
    Vector<Integer> indices = new Vector<Integer>();
 
    // Loop to traverse String
    for (int i = 0; i < S.length(); i++) {
      if (S.charAt(i) == '1')
        indices.add(i);
    }
 
    // Loop to reverse the
    // index vector
    for (int i = 1; i < indices.size(); i++)
 
      // Update maximum distance
      maxLen = Math.max(maxLen, indices.get(i) -
                        indices.get(i - 1));
 
    // Return Answer
    return maxLen == Integer.MIN_VALUE ? -1 : maxLen;
  }
 
  // Driver Code
  public static void main (String[] args)
  {
    String S = "1010010";
    System.out.println(maxDist(S));
  }
}
 
// This code is contributed by subhamsingh10.

# Python code for the above approach
 
# Function to find the maximum
# distance between two adjacent
# 1's in a given binary string
def maxDist(S):
 
    # Stores the required answer
    maxLen = 10 ** -9
 
    # Vector to store indices
    indices = []
 
    # Loop to traverse string
    for i in range(len(S)):
        if S[i] == "1":
            indices.append(i)
 
    # Loop to reverse the
    # index vector
    for i in range(1, len(indices)):
 
        # Update maximum distance
        maxLen = max(maxLen, indices[i] - indices[i - 1])
 
    # Return Answer
    return -1 if (maxLen == 10 ** -9) else maxLen
 
# Driver Code
S = "1010010"
print(maxDist(S))
 
# This code is contributed by gfgking

// C# program for above approach
using System;
using System.Collections.Generic;
 
public class GFG
{
 
  // Function to find the maximum
  // distance between two adjacent
  // 1's in a given binary string
  static int maxDist(string S)
  {
 
    // Stores the required answer
    int maxLen = Int32.MinValue;
 
    // Vector to store indices
    List<int> indices = new List<int>();
 
    // Loop to traverse string
    for (int i = 0; i < S.Length; i++) {
      if (S[i] == '1')
        indices.Add(i);
    }
 
    // Loop to reverse the
    // index vector
    for (int i = 1; i < indices.Count; i++)
 
      // Update maximum distance
      maxLen = Math.Max(maxLen, indices[i] -
                        indices[i - 1]);
 
    // Return Answer
    if(maxLen == Int32.MinValue)
      return  -1;
    else
      return maxLen;
  }
 
  // Driver code
  static public void Main ()
  {
 
    string S = "1010010";
    Console.WriteLine(maxDist(S));
  }
}
// This code is contributed by hrithikgarg03188

  <script>
      // JavaScript code for the above approach
 
      // Function to find the maximum
      // distance between two adjacent
      // 1's in a given binary string
      function maxDist(S)
      {
       
          // Stores the required answer
          let maxLen = Number.MIN_VALUE;
 
          // Vector to store indices
          let indices = [];
 
          // Loop to traverse string
          for (let i = 0; i < S.length; i++) {
              if (S[i] == '1')
                  indices.push(i);
          }
 
          // Loop to reverse the
          // index vector
          for (let i = 1; i < indices.length; i++)
 
              // Update maximum distance
              maxLen = Math.max(maxLen, indices[i] -
                  indices[i - 1]);
 
          // Return Answer
          return maxLen == Number.MIN_VALUE ? -1 : maxLen;
      }
 
      // Driver Code
      let S = "1010010";
      document.write(maxDist(S));
 
// This code is contributed by Potta Lokesh
  </script>

3

Complejidad de Tiempo: O(N)
Espacio Auxiliar: O(N) donde N es la longitud de la String Binaria.

 Enfoque de uso eficiente del espacio: el enfoque anterior también se puede implementar sin usar ningún espacio adicional (vector). El único cambio es lograr la distancia máxima mediante el almacenamiento riguroso de diferencias y la actualización cada vez que encontramos 1 en la string binaria.

// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum
// distance between two adjacent
// 1's in a given binary string
int maxDist(string S)
{
    // Stores the required answer
    int maxLen=0,i,start=0;
 
    // Loop to find first occurrence of '1' string
    for ( i = 0; i < S.length(); i++) {
        if (S[i] == '1')
        {
            start=i;
            break;
        }
    }
 
    // Loop to traverse remaining
    // indices of character '1'
    for (; i < S.length(); i++){
     
        // Update maximum distance
            if (S[i] == '1')
        {
            maxLen=max(maxLen,i-start);
            start=i;
        }
    }       
 
    // Return Answer
    return maxLen == 0 ? -1 : maxLen;
}
 
// Driver Code
int main()
{
    string S = "100000";
    cout << maxDist(S);
    return 0;
}

// Java program of the above approach
 
import java.util.*;
 
class GFG{
 
// Function to find the maximum
// distance between two adjacent
// 1's in a given binary String
static int maxDist(String S)
{
    // Stores the required answer
    int maxLen=0,i,start=0;
 
    // Loop to find first occurrence of '1' String
    for ( i = 0; i < S.length(); i++) {
        if (S.charAt(i) == '1')
        {
            start=i;
            break;
        }
    }
 
    // Loop to traverse remaining
    // indices of character '1'
    for (; i < S.length(); i++){
     
        // Update maximum distance
            if (S.charAt(i) == '1')
        {
            maxLen=Math.max(maxLen,i-start);
            start=i;
        }
    }       
 
    // Return Answer
    return maxLen == 0 ? -1 : maxLen;
}
 
// Driver Code
public static void main(String[] args)
{
    String S = "100000";
    System.out.print(maxDist(S));
}
}
 
// This code contributed by Rajput-Ji

// C# program of the above approach
using System;
public class GFG {
 
  // Function to find the maximum
  // distance between two adjacent
  // 1's in a given binary String
  static public int maxDist(String S)
  {
 
    // Stores the required answer
    int maxLen = 0, i, start = 0;
 
    // Loop to find first occurrence of '1' String
    for (i = 0; i < S.Length; i++) {
      if (S[i] == '1') {
        start = i;
        break;
      }
    }
 
    // Loop to traverse remaining
    // indices of character '1'
    for (; i < S.Length; i++) {
 
      // Update maximum distance
      if (S[i] == '1') {
        maxLen = Math.Max(maxLen, i - start);
        start = i;
      }
    }
 
    // Return Answer
    return maxLen == 0 ? -1 : maxLen;
  }
 
  // Driver Code
  public static void Main(String[] args) {
    String S = "100000";
    Console.Write(maxDist(S));
  }
}
 
// This code is contributed by Rajput-Ji

<script>
// javascript program of the above approach   
// Function to find the maximum
    // distance between two adjacent
    // 1's in a given binary String
    function maxDist( S)
    {
     
        // Stores the required answer
        var maxLen = 0, i, start = 0;
 
        // Loop to find first occurrence of '1' String
        for (i = 0; i < S.length; i++) {
            if (S.charAt(i) == '1') {
                start = i;
                break;
            }
        }
 
        // Loop to traverse remaining
        // indices of character '1'
        for (; i < S.length; i++) {
 
            // Update maximum distance
            if (S.charAt(i) == '1') {
                maxLen = Math.max(maxLen, i - start);
                start = i;
            }
        }
 
        // Return Answer
        return maxLen == 0 ? -1 : maxLen;
    }
 
    // Driver Code
        var S = "100000";
        document.write(maxDist(S));
 
// This code is contributed by Rajput-Ji
</script>

# Python program of the above approach
 
 
 
 
 
# Function to find the maximum
# distance between two adjacent
# 1's in a given binary String
def maxDist(S):
    # Stores the required answer
    maxLen = 0;
    start = 0;
 
    # Loop to find first occurrence of '1' String
    for i in range(len(S)):
        if (S[i] == '1'):
            start = i;
            break;
         
     
 
    # Loop to traverse remaining
    # indices of character '1'
    for i in range(start,len(S)):
 
        # Update maximum distance
        if (S[i] == '1'):
            maxLen = max(maxLen, i - start);
            start = i;
         
     
 
    # Return Answer
    if(maxLen == 0):
        return -1;
    else:
        return maxLen;
 
 
# Driver Code
if __name__ == '__main__':
    S = "100000";
    print(maxDist(S));
 
 
# This code contributed by Rajput-Ji

-1

Complejidad de tiempo: O(N)

Espacio Auxiliar: O(1)    donde N es la longitud de la String Binaria.