Dada una string binaria S que consta de tamaño N , la tarea es encontrar el número máximo de subsecuencias binarias de la forma «010..» de longitud de al menos 2 que se pueden eliminar de la string dada S .
Ejemplos:
Entrada: S = “110011010”
Salida: 3
Explicación: Las
siguientes son las subsecuencias eliminadas:
Operación 1: Elija la subsecuencia como “01” de los índices {2, 4}, y al eliminarla se modifica la string S = “1101010”.
Operación 2: Elige la subsecuencia como “01” de índices {2, 3}, y al borrarla se modifica la string S = “11010”.
Operación 3: Elige la subsecuencia como “01” de los índices {2, 3}, y al borrarla se modifica la string S = “110”.
De las observaciones anteriores, el número máximo de veces que se elimina la subsecuencia es 3.Entrada: S = “00111110011”
Salida: 4
Enfoque: el problema dado se puede resolver eliminando la subsecuencia de tipo «01» cada vez para maximizar el número de subsecuencias eliminadas. Por lo tanto, esto se puede mantener manteniendo una variable que almacene el recuento del número de caracteres 0 . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, diga cnt como 0 para almacenar el recuento de la cantidad de 0 que se han producido en la string.
- Inicialice la variable, diga ans como 0 para contar el número total de operaciones de eliminación realizadas.
- Recorra la string , S usando la variable i y realice los siguientes pasos:
- Si el valor de S[i] es X , entonces incremente el valor de cnt en 1 .
- De lo contrario, si el valor de cnt es mayor que 0 , disminuya el valor de cnt e incremente el valor de ans en 1.
- Después de completar 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 <iostream>
using namespace std;
// Function to count the maximum number
// of operations performed on the string
void countOperations(string S)
{
// Size of the string
int n = S.length();
// Stores the maximum number of
// operations performed
int ans = 0;
// Stores the count of 'X' occurred
// so far
int cnt = 0;
// Traverse the string
for (int i = 0; i < n; i++) {
// Check if current char
// is 'X'
if (S[i] == '0') {
cnt++;
}
else {
// Check if the value of
// cnt is greater than 0
if (cnt > 0) {
// Decrement the value
// of cnt
cnt--;
// Increment the value
// of ans
ans++;
}
}
}
// Print the value of ans
cout << ans;
}
// Driver Code
int main()
{
string S = "110011010";
countOperations(S);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG
{
// Function to count the maximum number
// of operations performed on the string
public static void countOperations(String S)
{
// Size of the string
int n = S.length();
// Stores the maximum number of
// operations performed
int ans = 0;
// Stores the count of 'X' occurred
// so far
int cnt = 0;
// Traverse the string
for (int i = 0; i < n; i++) {
// Check if current char
// is 'X'
if (S.charAt(i) == '0') {
cnt++;
}
else {
// Check if the value of
// cnt is greater than 0
if (cnt > 0) {
// Decrement the value
// of cnt
cnt--;
// Increment the value
// of ans
ans++;
}
}
}
// Print the value of ans
System.out.println(ans);
}
// Driver code
public static void main (String[] args)
{
String S = "110011010";
countOperations(S);
}
}
// This code is contributed by Manu Pathria
Python3
# Python program for the above approach # Function to count the maximum number # of operations performed on the string def countOperations(S): # Size of the string n = len(S) # Stores the maximum number of # operations performed ans = 0 # Stores the count of 'X' occurred # so far cnt = 0 # Traverse the string for i in range(n): # Check if current char # is 'X' if (S[i] == '0'): cnt+=1 else: # Check if the value of # cnt is greater than 0 if (cnt > 0): # Decrement the value # of cnt cnt-=1 # Increment the value # of ans ans+=1 # Print value of ans print (ans) # Driver Code if __name__ == '__main__': S = "110011010" countOperations(S) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
class GFG
{
// Function to count the maximum number
// of operations performed on the string
public static void countOperations(string S)
{
// Size of the string
int n = S.Length;
// Stores the maximum number of
// operations performed
int ans = 0;
// Stores the count of 'X' occurred
// so far
int cnt = 0;
// Traverse the string
for (int i = 0; i < n; i++) {
// Check if current char
// is 'X'
if (S[i] == '0') {
cnt++;
}
else {
// Check if the value of
// cnt is greater than 0
if (cnt > 0) {
// Decrement the value
// of cnt
cnt--;
// Increment the value
// of ans
ans++;
}
}
}
// Print the value of ans
Console.Write(ans);
}
// Driver code
public static void Main (string[] args)
{
string S = "110011010";
countOperations(S);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript Program for the above approach
// Function to count the maximum number
// of operations performed on the string
function countOperations(S) {
// Size of the string
let n = S.length;
// Stores the maximum number of
// operations performed
let ans = 0;
// Stores the count of 'X' occurred
// so far
let cnt = 0;
// Traverse the string
for (let i = 0; i < n; i++) {
// Check if current char
// is 'X'
if (S[i] == '0') {
cnt++;
}
else {
// Check if the value of
// cnt is greater than 0
if (cnt > 0) {
// Decrement the value
// of cnt
cnt--;
// Increment the value
// of ans
ans++;
}
}
}
// Print the value of ans
document.write(ans);
}
// Driver Code
let S = "110011010";
countOperations(S);
// This code is contributed by Potta Lokesh
</script>
3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por manupathria y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA