Posición más lejana que se puede alcanzar en una string binaria en K saltos saltando en dígitos alternos

Dada una string binaria S de longitud N y un entero K , la tarea es calcular la posición más lejana que se puede alcanzar a partir de la primera posición en exactamente K saltos.
Se puede hacer un salto del índice i al j solo si:

• yo != j
• Si el carácter en uno de ellos es ‘0’ y en otro es ‘1’.

Ejemplos :

Entrada : S = “100101”, K = 2
Salida : 6
Explicación : Se pueden tomar los siguientes pasos: 1 -> 5 -> 6, por lo tanto, el sexto índice se puede alcanzar en exactamente 2 saltos

Entrada : S = “10111”, K = 1
Salida : 2
Explicación : Se pueden tomar los siguientes pasos: 1 -> 2, por lo tanto, se puede alcanzar el segundo índice en exactamente 2 saltos

Enfoque: La principal observación del problema es que los patrones continuos de 0 y 1 se pueden reemplazar con un solo 0 o un solo 1 porque no se puede saltar entre caracteres similares. Después de reemplazar estos patrones continuos de 0 y 1 , ahora, uno puede simplemente verificar si el nuevo patrón dice que la string formada es menor que igual a K , entonces no es posible alcanzar algún punto con K movimientos, de lo contrario, la posición es simplemente la primera posicióndesde la derecha en el patrón real que contiene el carácter str[K] .

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

• Iterar desde el principio hasta el final de la string dada i = 0 a i = N-1 y generar una nueva string str después de reemplazar todos los subpatrones continuos de 0 con un solo 0 y de 1 con un solo 1.
• Ahora, verifique si la longitud de la string recién formada es menor que igual a K y luego imprima -1
• De lo contrario, si la longitud de la string recién formada es mayor que K, simplemente imprima la posición basada en 1 del carácter str[K] desde la derecha.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the farthest point
void get(string s, int k)
{
    // Store the answer
    int ans = 0;
 
    // Find the new string str
    string str = "";
    str += s[0];
 
    // Variables to count the zeroes and ones
    int cnt1 = 0, cnt0 = 0;
    int n = s.length();
 
    // Boolean variable to keep track of the subpattern
    bool isOne;
 
    if (s[0] == '0')
        isOne = false;
 
    // Iterate over the string and remove the
    // continuous patterns of 0s and 1s
    for (int i = 1; i < n; i++) {
        if (s[i] == '0' && isOne) {
            str += s[i];
            isOne = !isOne;
        }
        else if (s[i] == '1' && !isOne) {
            str += s[i];
            isOne = !isOne;
        }
    }
 
    // Count the number of zeroes and ones
    for (int i = 0; i < n; i++) {
        if (str[i] == '0')
            cnt0++;
        else
            cnt1++;
    }
 
    // Check if the K jumps are not possible
    if (str.length() <= k) {
        cout << -1 << endl;
        return;
    }
 
    // If K jumps are possible
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == str[k]) {
            ans = i + 1;
            break;
        }
    }
    cout << ans + 1 << endl;
}
 
// Driver Code
int main()
{
    string s = "100101";
    int k = 2;
    get(s, k);
    return 0;
}

// Java program for the above approach
import java.util.*;
public class GFG
{
// Function to find the farthest point
static void get(String s, int k)
{
    // Store the answer
    int ans = 0;
 
    // Find the new string str
    String str = "";
    str += s.charAt(0);
 
    // Variables to count the zeroes and ones
    int cnt1 = 0, cnt0 = 0;
    int n = s.length();
 
    // Boolean variable to keep track of the subpattern
    boolean isOne = false;
 
    if (s.charAt(0) == '0')
        isOne = false;
 
    // Iterate over the string and remove the
    // continuous patterns of 0s and 1s
    for (int i = 1; i < n; i++) {
        if (s.charAt(i) == '0' && isOne) {
            str += s.charAt(i);
            isOne = !isOne;
        }
        else if (s.charAt(i) == '1' && !isOne) {
            str += s.charAt(i);
            isOne = !isOne;
        }
    }
 
    // Count the number of zeroes and ones
    for (int i = 0; i < str.length(); i++) {
        if (str.charAt(i) == '0')
            cnt0++;
        else
            cnt1++;
    }
 
    // Check if the K jumps are not possible
    if (str.length() <= k) {
        System.out.print(-1);
        return;
    }
 
    // If K jumps are possible
    for (int i = n - 1; i >= 0; i--) {
        if (s.charAt(i) == str.charAt(k)) {
            ans = i + 1;
            break;
        }
    }
    System.out.print(ans + 1);
}
 
// Driver Code
public static void main(String args[])
{
    String s = "100101";
    int k = 2;
    get(s, k);
}
}
// This code is contributed by Samim Hossain Mondal

# Python3 program for the above approach
 
# Function to find the farthest point
def get(s, k) :
 
    # Store the answer
    ans = 0;
 
    # Find the new string str
    string = "";
    string += s[0];
 
    # Variables to count the zeroes and ones
    cnt1 = 0; cnt0 = 0;
    n = len(s);
 
    # Boolean variable to keep track of the subpattern
    isOne=False;
 
    if (s[0] == '0') :
        isOne = False;
 
    # Iterate over the string and remove the
    # continuous patterns of 0s and 1s
    for i in range(1, n) :
        if (s[i] == '0' and isOne) :
            string += s[i];
            isOne = not isOne;
         
        elif (s[i] == '1' and (not isOne)) :
            string += s[i];
            isOne = not isOne;
 
    # Count the number of zeroes and ones
    for i in range(len(string)) :
        if (string[i] == '0') :
            cnt0 += 1;
        else :
            cnt1 += 1;
 
    # Check if the K jumps are not possible
    if (len(string) <= k) :
        print(-1) ;
        return;
 
    # If K jumps are possible
    for i in range(n - 1, -1, -1) :
         
        if (s[i] == string[k]) :
            ans = i + 1;
            break;
    print(ans + 1);
 
 
# Driver Code
if __name__ ==  "__main__" :
 
    s = "100101";
    k = 2;
    get(s, k);
 
    # This code is contributed by AnkThon

// C# program for the above approach
using System;
class GFG
{
// Function to find the farthest point
static void get(string s, int k)
{
    // Store the answer
    int ans = 0;
 
    // Find the new string str
    string str = "";
    str += s[0];
 
    // Variables to count the zeroes and ones
    int cnt1 = 0, cnt0 = 0;
    int n = s.Length;
 
    // Bool variable to keep track of the subpattern
    bool isOne = false;
 
    if (s[0] == '0')
        isOne = false;
 
    // Iterate over the string and remove the
    // continuous patterns of 0s and 1s
    for (int i = 1; i < n; i++) {
        if (s[i] == '0' && isOne) {
            str += s[i];
            isOne = !isOne;
        }
        else if (s[i] == '1' && !isOne) {
            str += s[i];
            isOne = !isOne;
        }
    }
 
    // Count the number of zeroes and ones
    for (int i = 0; i < str.Length; i++) {
        if (str[i] == '0')
            cnt0++;
        else
            cnt1++;
    }
 
    // Check if the K jumps are not possible
    if (str.Length <= k) {
        Console.Write(-1);
        return;
    }
 
    // If K jumps are possible
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == str[k]) {
            ans = i + 1;
            break;
        }
    }
    Console.Write(ans + 1);
}
 
// Driver Code
public static void Main()
{
    string s = "100101";
    int k = 2;
    get(s, k);
}
}
// This code is contributed by Samim Hossain Mondal

<script>
        // JavaScript Program to implement
        // the above approach
 
        // Function to find the farthest point
        function get(s, k)
        {
         
            // Store the answer
            let ans = 0;
 
            // Find the new string str
            let str = "";
            str += s[0];
 
            // Variables to count the zeroes and ones
            let cnt1 = 0, cnt0 = 0;
            let n = s.length;
 
            // Boolean variable to keep track of the subpattern
            let isOne;
 
            if (s[0] == '0')
                isOne = false;
 
            // Iterate over the string and remove the
            // continuous patterns of 0s and 1s
            for (let i = 1; i < n; i++) {
                if (s[i] == '0' && isOne) {
                    str += s[i];
                    isOne = !isOne;
                }
                else if (s[i] == '1' && !isOne) {
                    str += s[i];
                    isOne = !isOne;
                }
            }
 
            // Count the number of zeroes and ones
            for (let i = 0; i < n; i++) {
                if (str[i] == '0')
                    cnt0++;
                else
                    cnt1++;
            }
 
            // Check if the K jumps are not possible
            if (str.length <= k) {
                document.write(-1 + '<br>');
                return;
            }
 
            // If K jumps are possible
            for (let i = n - 1; i >= 0; i--) {
                if (s[i] == str[k]) {
                    ans = i + 1;
                    break;
                }
            }
            document.write(ans + 1 + '<br>');
        }
 
        // Driver Code
 
        let s = "100101";
        let k = 2;
        get(s, k);
 
    // This code is contributed by Potta Lokesh
    </script>

6

Complejidad de Tiempo : O(N)
Espacio Auxiliar : O(1)