Dada una string binaria S , la tarea es encontrar la longitud máxima de las substrings necesarias para cambiar repetidamente para hacer que todos los caracteres de una string binaria sean iguales a ‘0’ .
Ejemplos:
Entrada: S = “010”
Salida: 2
Explicación:
A continuación se muestra el orden de inversión de la substring de al menos K para el valor de K como 2:
- Voltear la substring S[0, 2] de longitud 3(>= K) modifica la string S a «101».
- Voltear la substring S[0, 1] de longitud 2(>= K) modifica la string S a “011”.
- Voltear la substring S[1, 2] de longitud 2(>= K) modifica la string S a «000».
Para el valor de K como 2 (que es el valor máximo posible) todos los caracteres de la string pueden convertirse en 0. Por lo tanto, imprima 2.
Entrada: S = “00001111”
Salida: 4
Enfoque: el problema dado se puede resolver atravesando la string S dada , ahora, si en algún punto los caracteres adyacentes no son los mismos, cambie una substring LHS o RHS . Para eso, tome la longitud máxima de LHS y RHS . Puede haber múltiples lugares adyacentes donde los caracteres no son iguales. Para cada par de substrings , el máximo requerido será diferente. Ahora, para cambiar todos los caracteres a ‘0’, tome el mínimo entre todos esos máximos. Siga los pasos a continuación para resolver el problema:
- Inicialice la variable, digamos ans como N que almacena el valor máximo posible de K .
- Iterar sobre el rango [0, N – 1) usando la variable i y realizar los siguientes pasos:
- Si el valor de s[i] y s[i + 1] no es el mismo, actualice el valor de ans al mínimo de ans o al máximo de (i + 1) o (N – i – 1) .
- Después de realizar los pasos anteriores, imprima el valor de ans como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum value of K
// such that flipping substrings of size
// at least K make all characters 0s
int maximumK(string& S)
{
int N = S.length();
// Stores the maximum value of K
int ans = N;
int flag = 0;
// Traverse the given string S
for (int i = 0; i < N - 1; i++) {
// Store the minimum of the
// maximum of LHS and RHS length
if (S[i] != S[i + 1]) {
// Flip performed
flag = 1;
ans = min(ans, max(i + 1,
N - i - 1));
}
}
// If no flips performed
if (flag == 0)
return 0;
// Return the possible value of K
return ans;
}
// Driver Code
int main()
{
string S = "010";
cout << maximumK(S);
return 0;
}
Java
// Java code for above approach
import java.util.*;
class GFG{
// Function to find the maximum value of K
// such that flipping substrings of size
// at least K make all characters 0s
static int maximumK(String S)
{
int N = S.length();
// Stores the maximum value of K
int ans = N;
int flag = 0;
// Traverse the given string S
for (int i = 0; i < N - 1; i++) {
// Store the minimum of the
// maximum of LHS and RHS length
if (S.charAt(i) != S.charAt(i + 1)) {
// Flip performed
flag = 1;
ans = Math.min(ans, Math.max(i + 1,
N - i - 1));
}
}
// If no flips performed
if (flag == 0)
return 0;
// Return the possible value of K
return ans;
}
// Driver Code
public static void main(String[] args)
{
String S = "010";
System.out.print(maximumK(S));
}
}
// This code is contributed by target_2.
Python3
# Python 3 program for the above approach # Function to find the maximum value of K # such that flipping substrings of size # at least K make all characters 0s def maximumK(S): N = len(S) # Stores the maximum value of K ans = N flag = 0 # Traverse the given string S for i in range(N - 1): # Store the minimum of the # maximum of LHS and RHS length if (S[i] != S[i + 1]): # Flip performed flag = 1 ans = min(ans, max(i + 1,N - i - 1)) # If no flips performed if (flag == 0): return 0 # Return the possible value of K return ans # Driver Code if __name__ == '__main__': S = "010" print(maximumK(S)) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# code for the above approach
using System;
public class GFG {
// Function to find the maximum value of K
// such that flipping substrings of size
// at least K make all characters 0s
static int maximumK(String S)
{
int N = S.Length;
// Stores the maximum value of K
int ans = N;
int flag = 0;
// Traverse the given string S
for (int i = 0; i < N - 1; i++) {
// Store the minimum of the
// maximum of LHS and RHS length
if (S[i] != S[i + 1]) {
// Flip performed
flag = 1;
ans = Math.Min(ans,
Math.Max(i + 1, N - i - 1));
}
}
// If no flips performed
if (flag == 0)
return 0;
// Return the possible value of K
return ans;
}
// Driver Code
static public void Main()
{
// Code
string S = "010";
Console.Write(maximumK(S));
}
}
// This code is contributed by Potta Lokesh
Javascript
<script>
// Javascript program for the above approach
// Function to find the maximum value of K
// such that flipping substrings of size
// at least K make all characters 0s
function maximumK(S)
{
let N = S.length;
// Stores the maximum value of K
let ans = N;
let flag = 0;
// Traverse the given string S
for (let i = 0; i < N - 1; i++)
{
// Store the minimum of the
// maximum of LHS and RHS length
if (S[i] != S[i + 1])
{
// Flip performed
flag = 1;
ans = Math.min(ans, Math.max(i + 1, N - i - 1));
}
}
// If no flips performed
if (flag == 0) return 0;
// Return the possible value of K
return ans;
}
// Driver Code
let S = "010";
document.write(maximumK(S));
// This code is contributed by gfgking.
</script>
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA