Ventana más pequeña que contiene 0, 1 y 2

Posted on by Rudeus Greyrat

Dada una string S de tamaño N que consta de los caracteres 0, 1 y 2, la tarea es encontrar la longitud de la substring más pequeña de la string S que contiene los tres caracteres 0, 1 y 2. Si no existe tal substring, entonces devolver -1.

Ejemplos:

Entrada: S = “01212”
Salida: 3
Explicación: La substring 012 es la substring más pequeña
que contiene los caracteres 0, 1 y 2.

Entrada:  S = “12121”
Salida: -1
Explicación:  Como el carácter 0 no está presente en la
string S, no existe ninguna substring que contenga
los tres caracteres 0, 1 y 2
. Por lo tanto, la respuesta es -1 en este caso.

 

Enfoque: La idea del enfoque es como se menciona a continuación:

Utilice tres punteros para almacenar los índices de los elementos 0, 1 y 2. Cuando se encuentran los tres elementos, la distancia entre el máximo y el mínimo de ellos es la ventana de tamaño mínimo.
Continúe actualizando los punteros cada vez que alguno de ellos se encuentre nuevamente y calcule el tamaño de la nueva ventana.

Siga la ilustración a continuación para una mejor comprensión.

Ilustración:

Considere S = “01212” y los tres punteros sean índice cero, índice uno y dos índices y configúrelos todos en -1 inicialmente.

Cuando i = 0:
        => S[i] = ‘0’. zeroindex = 0, oneindex = -1, twoindex = -1
        => No se encuentran todos los valores. Así que ninguna ventana es posible

Cuando i = 1:
        => S[i] = ‘1’. zeroindex = 0, oneindex = 1, twoindex = -1
        => No se encuentran todos los valores. Así que ninguna ventana es posible

Cuando i = 2:
        => S[i] = ‘2’. zeroindex = 0, oneindex = 1, twoindex = 2
        => Se encuentran todos los valores. 
        => El máximo es twoindex = 2. El mínimo es zeroindex = 0.
        => Entonces, el tamaño de la ventana = (2 – 0 + 1) = 3 .
        => Tamaño mínimo de ventana = 3

Cuando i = 3:
        => S[i] = ‘1’. zeroindex = 0, oneindex = 3, twoindex = 2
        => Se encuentran todos los valores. 
        => El máximo es oneindex = 3. El mínimo es zeroindex = 0.
        => Así que el tamaño de la ventana = (3 – 0 + 1) = 4 .
        => Tamaño mínimo de ventana = min (3, 4) = 3

Cuando i = 4:
        => S[i] = ‘2’. zeroindex = 0, oneindex = 3, twoindex = 4
        => Se encuentran todos los valores. 
        => El máximo es twoindex = 4. El mínimo es zeroindex = 0.
        => Entonces, el tamaño de la ventana = (4 – 0 + 1) = 5 .
        => Tamaño mínimo de ventana = min(3, 5) = 3

Entonces el tamaño de la ventana más pequeña es 3

Siga los pasos a continuación para resolver el problema:

  • Tome tres variables cero , uno y dos para verificar si 0, 1 y 2 se encuentran en la ventana o no.
  • Tome tres variables zeroindex , oneindex y twoindex que almacenarán índices de 0, 1 y 2 cuando los encontremos.
  • Ejecute el bucle for para toda la longitud de String:
    • Actualice los índices de los valores encontrados.
    • Actualice la longitud de la ventana, si se encuentran tres de ellas.
    • La longitud será la diferencia entre el máximo y el mínimo de los índices 0, 1 y 2.
  • Y si los tres valores, es decir, 0, 1, 2 no se encuentran después de que finaliza el recorrido, en ese caso devuelve ‘-1’.

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

C++

// C++ program for above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the length of the smallest substring
int smallestSubstring(string S)
{
    int res = INT_MAX;
    // To check 0, 1 and 2
    bool zero = false, one = false, two = false;
    // To store indexes of 0, 1 and 2
    int zeroindex, oneindex, twoindex;
    for (int i = 0; i < S.length(); i++) {
        if (S[i] == '0') {
            zero = true;
            zeroindex = i;
        }
        else if (S[i] == '1') {
            one = true;
            oneindex = i;
        }
        else if (S[i] == '2') {
            two = true;
            twoindex = i;
        }
 
        // Calculating length
        if (zero and one and two)
            res = min(res,
                      max({ zeroindex, oneindex, twoindex })
                          - min({ zeroindex, oneindex, twoindex }));
    }
 
    // In case if their is no substring that contains 0,1 and 2
    if (res == INT_MAX)
        return -1;
    return res + 1;
}
 
// Driver Code
int main()
{
    string S = "01212";
 
    // Function call
    cout << smallestSubstring(S);
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

C

// C program for above approach
 
#include <limits.h> // to use INT_MAX
#include <stdbool.h> //to use bool variable
#include <stdio.h>
 
// function to calculate max of two numbers
int min_two(int a, int b)
{
    if (a <= b)
        return a;
    else
        return b;
}
 
// function to calculate max of three numbers
int max_three(int a, int b, int c)
{
    if (a >= b && a >= c)
        return a;
    else if (b > a && b >= c)
        return b;
    else if (c > a && c > b)
        return c;
}
 
// function to calculate min of three numbers
int min_three(int a, int b, int c)
{
    if (a <= b && a <= c)
        return a;
    else if (b < a && b <= c)
        return b;
    else if (c < a && c < b)
        return c;
}
 
// Function to find the length of
// the smallest substring
int smallestSubstring(char S[], int n)
{
    int res = INT_MAX;
 
    // To check 0, 1 and 2
    bool zero = 0, one = 0, two = 0;
 
    // To store indexes of 0, 1 and 2
    int zeroindex, oneindex, twoindex;
    for (int i = 0; i < n; i++) {
        if (S[i] == '0') {
            zero = true;
            zeroindex = i;
        }
        else if (S[i] == '1') {
            one = true;
            oneindex = i;
        }
        else if (S[i] == '2') {
            two = true;
            twoindex = i;
        }
 
        // Calculating length
        if (zero && one && two)
            res = min_two( res,
                     max_three(zeroindex, oneindex, twoindex)
                    - min_three(zeroindex, oneindex, twoindex));
    }
 
    // In case if their is no substring that contains 0,1 and 2
    if (res == INT_MAX)
        return -1;
    return res + 1;
}
 
// Driver Code
int main()
{
    int n = 5; // size of string
    char S[] = "01212";
 
    int ans = smallestSubstring(S, n);
    // Function call
    printf("%d", ans);
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

Java

// Java program for above approach
import java.util.*;
class GFG {
 
    // Function to find the length of the smallest substring
    public static int smallestSubstring(String S)
    {
        int res = Integer.MAX_VALUE;
 
        // To check 0, 1 and 2
        boolean zero = false, one = false, two = false;
 
        // To store indexes of 0, 1 and 2
        int zeroindex = 0, oneindex = 0, twoindex = 0;
        for (int i = 0; i < S.length(); i++) {
            if (S.charAt(i) == '0') {
                zero = true;
                zeroindex = i;
            }
            else if (S.charAt(i) == '1') {
                one = true;
                oneindex = i;
            }
            else if (S.charAt(i) == '2') {
                two = true;
                twoindex = i;
            }
 
            // Calculating length
            if (zero && one && two)
                res = Math.min( res,
                    Math.max(zeroindex,Math.max(oneindex, twoindex))
                  - Math.min( zeroindex,Math.min(oneindex, twoindex)));
        }
 
        // In case if their is no substring that contains 0,1 and 2
        if (res == Integer.MAX_VALUE)
            return -1;
        return res + 1;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        String S = "01212";
        // Function call
        System.out.print(smallestSubstring(S));
    }
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

Python3

# Python code for the above approach
 
# Function to find the length of the smallest substring
 
 
def smallestSubstring(S):
    res = 999999
 
    # To check 0, 1 and 2
    zero = 0
    one = 0
    two = 0
 
    # To store indexes of 0, 1 and 2
    zeroindex = 0
    oneindex = 0
    twoindex = 0
    for i in range(len(S)):
        if (S[i] == '0'):
            zero = 1
            zeroindex = i
 
        elif (S[i] == '1'):
            one = 1
            oneindex = i
 
        elif (S[i] == '2'):
            two = 1
            twoindex = i
 
        # Calculating length
        if (zero and one and two):
            res = min(res,
                      max([zeroindex, oneindex, twoindex])
                      - min([zeroindex, oneindex, twoindex]))
 
    # In case if their is no substring that contains 0,1 and 2
    if (res == 999999):
        return -1
    return res + 1
 
 
# Driver Code
S = "01212"
 
# Function call
print(smallestSubstring(S))
 
# This code is contributed by Aditya Kumar (adityakumar129)

C#

// C# program for above approach
using System;
 
public class GFG {
 
    // Function to find the length of the smallest substring
    static int smallestSubstring(string S)
    {
        int res = Int32.MaxValue;
 
        // To check 0, 1 and 2
        bool zero = false, one = false, two = false;
 
        // To store indexes of 0, 1 and 2
        int zeroindex = 0, oneindex = 0, twoindex = 0;
        for (int i = 0; i < S.Length; i++) {
            if (S[i] == '0') {
                zero = true;
                zeroindex = i;
            }
            else if (S[i] == '1') {
                one = true;
                oneindex = i;
            }
            else if (S[i] == '2') {
                two = true;
                twoindex = i;
            }
 
            // Calculating length
            if (zero && one && two)
                res = Math.Min(res,
                    Math.Max( zeroindex, Math.Max(oneindex, twoindex))
                  - Math.Min( zeroindex, Math.Min(oneindex, twoindex)));
        }
 
        // In case if their is no substring that contains 0,1 and 2
        if (res == Int32.MaxValue)
            return -1;
        return res + 1;
    }
 
    // Driver Code
    static public void Main()
    {
        string S = "01212";
 
        // Function call
        Console.Write(smallestSubstring(S));
    }
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

Javascript

<script>
    // JavaScript program for above approach
    const INT_MAX = 2147483647;
 
    // Function to find the length of
    // the smallest substring
    const smallestSubstring = (S) => {
        let res = INT_MAX;
 
        // To check 0, 1 and 2
        let zero = false, one = false, two = false;
 
        // To store indexes of 0, 1 and 2
        let zeroindex, oneindex, twoindex;
        for (let i = 0; i < S.length; i++) {
            if (S[i] == '0') {
                zero = true;
                zeroindex = i;
            }
            else if (S[i] == '1') {
                one = true;
                oneindex = i;
            }
            else if (S[i] == '2') {
                two = true;
                twoindex = i;
            }
 
            // Calculating length
            if (zero && one && two)
                res = Math.min(res,
                    Math.max(...[zeroindex, oneindex, twoindex])
                  - Math.min(...[zeroindex, oneindex, twoindex]));
        }
 
        // In case if their is no substring that contains 0,1 and 2
        if (res == INT_MAX)
            return -1;
        return res + 1;
    }
 
    // Driver Code
    let S = "01212";
 
    // Function call
    document.write(smallestSubstring(S));
 
    // This code is contributed by Aditya Kumar (adityakumar129)
 
</script>
Producción

3

Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar N veces.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.

Publicación traducida automáticamente

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