Dada una string binaria S de longitud N y un entero K , la tarea es encontrar la substring distinta de cero más pequeña de S que se pueda mezclar para producir una string binaria divisible por 2 K . Si no existe tal substring, imprima -1 . Tenga en cuenta que K siempre es mayor que 0 .
Ejemplos:
Entrada: S = “100”, k = 1
Salida: 2 La
substring más pequeña que se puede mezclar es “10”.
Por tanto, la respuesta es 2.
Entrada: S = “1111”, k = 2
Salida: -1
Enfoque: Veamos la condición de que la permutación de una string sea divisible por 2 K .
- La string debe tener al menos K número de 0s .
- La string debe tener al menos un 1 .
Esto se puede implementar utilizando la técnica de dos punteros . Para cada índice i , intente encontrar el índice j más pequeño tal que la substring S[i…j-1] satisfaga las dos condiciones anteriores.
Digamos que el puntero izquierdo apunta al índice i y el puntero derecho apunta a j y ans almacena la longitud de la substring requerida más pequeña.
Si la condición no se cumple, entonces incremente j , de lo contrario incremente i .
Mientras itera, encuentre el mínimo (j – i) que satisfaga las dos condiciones anteriores y actualice la respuesta como ans = min(ans, j – i) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the length of the
// smallest substring divisible by 2^k
int findLength(string s, int k)
{
// To store the final answer
int ans = INT_MAX;
// Left pointer
int l = 0;
// Right pointer
int r = 0;
// Count of the number of zeros and
// ones in the current substring
int cnt_zero = 0, cnt_one = 0;
// Loop for two pointers
while (l < s.size() and r <= s.size()) {
// Condition satisfied
if (cnt_zero >= k and cnt_one >= 1) {
// Updated the answer
ans = min(ans, r - l);
// Update the pointer and count
l++;
if (s[l - 1] == '0')
cnt_zero--;
else
cnt_one--;
}
else {
// Update the pointer and count
if (r == s.size())
break;
if (s[r] == '0')
cnt_zero++;
else
cnt_one++;
r++;
}
}
if (ans == INT_MAX)
return -1;
return ans;
}
// Driver code
int main()
{
string s = "100";
int k = 2;
cout << findLength(s, k);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
static final int INT_MAX = Integer.MAX_VALUE;
// Function to return the length of the
// smallest substring divisible by 2^k
static int findLength(String s, int k)
{
// To store the final answer
int ans = INT_MAX;
// Left pointer
int l = 0;
// Right pointer
int r = 0;
// Count of the number of zeros and
// ones in the current substring
int cnt_zero = 0, cnt_one = 0;
// Loop for two pointers
while (l < s.length() && r <= s.length())
{
// Condition satisfied
if (cnt_zero >= k && cnt_one >= 1)
{
// Updated the answer
ans = Math.min(ans, r - l);
// Update the pointer and count
l++;
if (s.charAt(l - 1) == '0')
cnt_zero--;
else
cnt_one--;
}
else
{
// Update the pointer and count
if (r == s.length())
break;
if (s.charAt(r) == '0')
cnt_zero++;
else
cnt_one++;
r++;
}
}
if (ans == INT_MAX)
return -1;
return ans;
}
// Driver code
public static void main (String[] args)
{
String s = "100";
int k = 2;
System.out.println(findLength(s, k));
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach # Function to return the length of the # smallest subdivisible by 2^k def findLength(s, k): # To store the final answer ans = 10**9 # Left pointer l = 0 # Right pointer r = 0 # Count of the number of zeros and # ones in the current substring cnt_zero = 0 cnt_one = 0 # Loop for two pointers while (l < len(s) and r <= len(s)): # Condition satisfied if (cnt_zero >= k and cnt_one >= 1): # Updated the answer ans = min(ans, r - l) # Update the pointer and count l += 1 if (s[l - 1] == '0'): cnt_zero -= 1 else: cnt_one -= 1 else: # Update the pointer and count if (r == len(s)): break if (s[r] == '0'): cnt_zero += 1 else: cnt_one += 1 r += 1 if (ans == 10**9): return -1 return ans # Driver code s = "100" k = 2 print(findLength(s, k)) # This code is contributed by Mohit Kumar
C#
// C# implementation of the approach
using System;
class GFG
{
static int INT_MAX = int.MaxValue;
// Function to return the length of the
// smallest substring divisible by 2^k
static int findLength(string s, int k)
{
// To store the final answer
int ans = INT_MAX;
// Left pointer
int l = 0;
// Right pointer
int r = 0;
// Count of the number of zeros and
// ones in the current substring
int cnt_zero = 0, cnt_one = 0;
// Loop for two pointers
while (l < s.Length && r <= s.Length)
{
// Condition satisfied
if (cnt_zero >= k && cnt_one >= 1)
{
// Updated the answer
ans = Math.Min(ans, r - l);
// Update the pointer and count
l++;
if (s[l - 1] == '0')
cnt_zero--;
else
cnt_one--;
}
else
{
// Update the pointer and count
if (r == s.Length)
break;
if (s[r] == '0')
cnt_zero++;
else
cnt_one++;
r++;
}
}
if (ans == INT_MAX)
return -1;
return ans;
}
// Driver code
public static void Main ()
{
string s = "100";
int k = 2;
Console.WriteLine(findLength(s, k));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// Javascript implementation of the approach
// Function to return the length of the
// smallest substring divisible by 2^k
function findLength(s, k)
{
// To store the final answer
var ans = 1000000000;
// Left pointer
var l = 0;
// Right pointer
var r = 0;
// Count of the number of zeros and
// ones in the current substring
var cnt_zero = 0, cnt_one = 0;
// Loop for two pointers
while (l < s.length && r <= s.length) {
// Condition satisfied
if (cnt_zero >= k && cnt_one >= 1) {
// Updated the answer
ans = Math.min(ans, r - l);
// Update the pointer and count
l++;
if (s[l - 1] == '0')
cnt_zero--;
else
cnt_one--;
}
else {
// Update the pointer and count
if (r == s.length)
break;
if (s[r] == '0')
cnt_zero++;
else
cnt_one++;
r++;
}
}
if (ans == 1000000000)
return -1;
return ans;
}
// Driver code
var s = "100";
var k = 2;
document.write( findLength(s, k));
</script>
3
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA