Dada una string binaria S de longitud N , la tarea es encontrar la substring más larga que consiste en ‘1’ que solo están presentes en la string después de eliminar un carácter de la string .
Ejemplos:
Entrada: S = “1101”
Salida: 3
Explicación:
Eliminando S[0], S se modifica a “101”. La substring más larga posible de ‘1’ es 1.
Eliminando S[1], S se modifica a «101». La substring más larga posible de ‘1’ es 1.
Eliminando S[2], S se modifica a «111». La substring más larga posible de ‘1’ es 3.
Eliminando S[3], S se modifica a «110». La substring más larga posible de ‘1’ es 2.
Por lo tanto, la substring más larga posible de ‘1’ que se puede obtener es 3.Entrada: S = “011101101”
Salida: 5
Método 1: La idea es atravesar la string y buscar ‘0’ en la string dada. Para cada carácter que resulte ser ‘0’ , agregue la longitud de sus substrings adyacentes de ‘1’ . Imprime el máximo de todas las longitudes obtenidas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the length of the
// longest substring of '1's that can be
// obtained by deleting one character
int longestSubarray(string s)
{
// Add '0' at the end
s += '0';
// Iterator to traverse the string
int i;
// Stores maximum length
// of required substring
int res = 0;
// Stores length of substring of '1'
// preceding the current character
int prev_one = 0;
// Stores length of substring of '1'
// succeeding the current character
int curr_one = 0;
// Counts number of '0's
int numberOfZeros = 0;
// Traverse the string S
for (i = 0; i < s.length(); i++) {
// If current character is '1'
if (s[i] == '1') {
// Increase curr_one by one
curr_one += 1;
}
// Otherwise
else {
// Increment numberofZeros by one
numberOfZeros += 1;
// Count length of substring
// obtained y concatenating
// preceding and succeeding substrings of '1'
prev_one += curr_one;
// Store maximum size in res
res = max(res, prev_one);
// Assign curr_one to prev_one
prev_one = curr_one;
// Reset curr_one
curr_one = 0;
}
}
// If string contains only one '0'
if (numberOfZeros == 1) {
res -= 1;
}
// Return the answer
return res;
}
// Driver Code
int main()
{
string S = "1101";
cout << longestSubarray(S);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.Arrays;
class GFG{
// Function to calculate the length of the
// longest substring of '1's that can be
// obtained by deleting one character
static int longestSubarray(String s)
{
// Add '0' at the end
s += '0';
// Iterator to traverse the string
int i;
// Stores maximum length
// of required substring
int res = 0;
// Stores length of substring of '1'
// preceding the current character
int prev_one = 0;
// Stores length of substring of '1'
// succeeding the current character
int curr_one = 0;
// Counts number of '0's
int numberOfZeros = 0;
// Traverse the string S
for(i = 0; i < s.length(); i++)
{
// If current character is '1'
if (s.charAt(i) == '1')
{
// Increase curr_one by one
curr_one += 1;
}
// Otherwise
else
{
// Increment numberofZeros by one
numberOfZeros += 1;
// Count length of substring
// obtained y concatenating
// preceding and succeeding
// substrings of '1'
prev_one += curr_one;
// Store maximum size in res
res = Math.max(res, prev_one);
// Assign curr_one to prev_one
prev_one = curr_one;
// Reset curr_one
curr_one = 0;
}
}
// If string contains only one '0'
if (numberOfZeros == 1)
{
res -= 1;
}
// Return the answer
return res;
}
// Driver Code
public static void main (String[] args)
{
String S = "1101";
System.out.println(longestSubarray(S));
}
}
// This code is contributed by code_hunt
Python3
# Python3 program to implement # the above approach # Function to calculate the length of the # longest substring of '1's that can be # obtained by deleting one character def longestSubarray(s): # Add '0' at the end s += '0' # Iterator to traverse the string i = 0 # Stores maximum length # of required substring res = 0 # Stores length of substring of '1' # preceding the current character prev_one = 0 # Stores length of substring of '1' # succeeding the current character curr_one = 0 # Counts number of '0's numberOfZeros = 0 # Traverse the string S for i in range(len(s)): # If current character is '1' if (s[i] == '1'): # Increase curr_one by one curr_one += 1 # Otherwise else: # Increment numberofZeros by one numberOfZeros += 1 # Count length of substring # obtained y concatenating # preceding and succeeding # substrings of '1' prev_one += curr_one # Store maximum size in res res = max(res, prev_one) # Assign curr_one to prev_one prev_one = curr_one # Reset curr_one curr_one = 0 # If string contains only one '0' if (numberOfZeros == 1): res -= 1 # Return the answer return res # Driver Code if __name__ == '__main__': S = "1101" print(longestSubarray(S)) # This code is contributed by ipg2016107
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Function to calculate the length of the
// longest substring of '1's that can be
// obtained by deleting one character
static int longestSubarray(String s)
{
// Add '0' at the end
s += '0';
// Iterator to traverse the string
int i;
// Stores maximum length
// of required substring
int res = 0;
// Stores length of substring of '1'
// preceding the current character
int prev_one = 0;
// Stores length of substring of '1'
// succeeding the current character
int curr_one = 0;
// Counts number of '0's
int numberOfZeros = 0;
// Traverse the string S
for(i = 0; i < s.Length; i++)
{
// If current character is '1'
if (s[i] == '1')
{
// Increase curr_one by one
curr_one += 1;
}
// Otherwise
else
{
// Increment numberofZeros by one
numberOfZeros += 1;
// Count length of substring
// obtained y concatenating
// preceding and succeeding
// substrings of '1'
prev_one += curr_one;
// Store maximum size in res
res = Math.Max(res, prev_one);
// Assign curr_one to prev_one
prev_one = curr_one;
// Reset curr_one
curr_one = 0;
}
}
// If string contains only one '0'
if (numberOfZeros == 1)
{
res -= 1;
}
// Return the answer
return res;
}
// Driver Code
public static void Main(String[] args)
{
String S = "1101";
Console.WriteLine(longestSubarray(S));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// javascript program to implement
// the above approach
// Function to calculate the length of the
// longest substring of '1's that can be
// obtained by deleting one character
function longestSubarray(s)
{
// Add '0' at the end
s += '0';
// Iterator to traverse the string
let i;
// Stores maximum length
// of required substring
let res = 0;
// Stores length of substring of '1'
// preceding the current character
let prev_one = 0;
// Stores length of substring of '1'
// succeeding the current character
let curr_one = 0;
// Counts number of '0's
let numberOfZeros = 0;
// Traverse the string S
for(i = 0; i < s.length; i++)
{
// If current character is '1'
if (s[i] == '1')
{
// Increase curr_one by one
curr_one += 1;
}
// Otherwise
else
{
// Increment numberofZeros by one
numberOfZeros += 1;
// Count length of substring
// obtained y concatenating
// preceding and succeeding
// substrings of '1'
prev_one += curr_one;
// Store maximum size in res
res = Math.max(res, prev_one);
// Assign curr_one to prev_one
prev_one = curr_one;
// Reset curr_one
curr_one = 0;
}
}
// If string contains only one '0'
if (numberOfZeros == 1)
{
res -= 1;
}
// Return the answer
return res;
}
// Driver code
let S = "1101";
document.write(longestSubarray(S));
// This code is contributed by splevel62.
</script>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Método 2: un enfoque alternativo para resolver el problema es usar la técnica de ventana deslizante para encontrar la longitud máxima de la substring que contiene solo ‘1’ después de eliminar un solo carácter. Siga los pasos a continuación para resolver el problema:
- Inicialice 3 variables enteras i, j , con 0 y k con 1
- Iterar sobre los caracteres de la string S .
- Por cada carácter atravesado, compruebe si es ‘0’ o no. Si se determina que es cierto, disminuya k en 1 .
- Si k < 0 y el carácter en el i -ésimo índice es ‘0’ , incremente k e i en uno
- Incremente j en uno .
- Finalmente, imprima la longitud j – i – 1 después de recorrer completamente la string.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the length of the
// longest substring of '1's that can be
// obtained by deleting one character
int longestSubarray(string s)
{
// Initializing i and j as left and
// right boundaries of sliding window
int i = 0, j = 0, k = 1;
for (j = 0; j < s.size(); ++j) {
// If current character is '0'
if (s[j] == '0')
// Decrement k by one
k--;
// If k is less than zero and character
// at ith index is '0'
if (k < 0 && s[i++] == '0')
k++;
}
// Return result
return j - i - 1;
}
// Driver Code
int main()
{
string S = "011101101";
cout << longestSubarray(S);
return 0;
}
Java
// Java Program to implement
// the above approach
import java.util.*;
class GFG{
// Function to calculate the length of the
// longest subString of '1's that can be
// obtained by deleting one character
static int longestSubarray(String s)
{
// Initializing i and j as left and
// right boundaries of sliding window
int i = 0, j = 0, k = 1;
for (j = 0; j < s.length(); ++j)
{
// If current character is '0'
if (s.charAt(j) == '0')
// Decrement k by one
k--;
// If k is less than zero and character
// at ith index is '0'
if (k < 0 && s.charAt(i++) == '0')
k++;
}
// Return result
return j - i - 1;
}
// Driver Code
public static void main(String[] args)
{
String S = "011101101";
System.out.print(longestSubarray(S));
}
}
// This code contributed by gauravrajput1
Python3
# Python3 program to implement # the above approach # Function to calculate the length of the # longest substring of '1's that can be # obtained by deleting one character def longestSubarray(s): # Initializing i and j as left and # right boundaries of sliding window i = 0 j = 0 k = 1 for j in range(len(s)): # If current character is '0' if (s[j] == '0'): # Decrement k by one k -= 1 # If k is less than zero and character # at ith index is '0' if (k < 0 ): if s[i] == '0': k += 1 i += 1 j += 1 # Return result return j - i - 1 # Driver Code if __name__ == "__main__" : S = "011101101" print(longestSubarray(S)) # This code is contributed by AnkThon
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to calculate the length of the
// longest subString of '1's that can be
// obtained by deleting one character
static int longestSubarray(string s)
{
// Initializing i and j as left and
// right boundaries of sliding window
int i = 0, j = 0, k = 1;
for(j = 0; j < s.Length; ++j)
{
// If current character is '0'
if (s[j] == '0')
// Decrement k by one
k -= 1;
// If k is less than zero and character
// at ith index is '0'
if (k < 0 && s[i++] == '0')
k++;
}
// Return result
return j - i - 1;
}
// Driver Code
public static void Main(string[] args)
{
string S = "011101101";
Console.Write(longestSubarray(S));
}
}
// This code is contributed by AnkThon
Javascript
<script>
// Javascript Program to implement
// the above approach
// Function to calculate the length of the
// longest substring of '1's that can be
// obtained by deleting one character
function longestSubarray(s)
{
// Initializing i and j as left and
// right boundaries of sliding window
var i = 0, j = 0, k = 1;
for (j = 0; j < s.length; ++j) {
// If current character is '0'
if (s[j] == '0')
// Decrement k by one
k--;
// If k is less than zero and character
// at ith index is '0'
if (k < 0 && s[i++] == '0')
k++;
}
// Return result
return j - i - 1;
}
// Driver Code
var S = "011101101";
document.write( longestSubarray(S));
</script>
Producción:
5
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Akash_chowrasia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA