Longitud de los consecutivos más largos por un intercambio como máximo en una string binaria

Posted on by Rudeus Greyrat

Dada una string binaria de longitud  N . Se permite hacer como máximo un intercambio entre cualquier 0 y 1. La tarea es encontrar la longitud de los 1 consecutivos más largos que se pueden lograr.
Ejemplos: 
 

Input : str = "111011101"
Output : 7 
We can swap 0 at 4th with 1 at 10th position

Input : str = "111000"
Output : 3 
We cannot obtain more than 3 1's after

Enfoque : 
 

  1. Cuente todos los 1 en la array en una variable, digamos cnt_one .
  2. Mantenga dos vectores o arrays que almacenen los acumulativos de izquierda y derecha.
  3. Siempre que haya un 0: 
    • if ( izquierda[i-1]+derecha[i+1] < cnt_one ) store max_count = izquierda[i-1] + derecha [i+1] + 1 , ya que al intercambiar obtendremos uno extra en lugar de 0 .
    • else max_count = izquierda[i-1] + derecha[i+1] .
  4. La salida es el valor máximo de max_count que se puede lograr.

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

C++

// C++ program to find length of longest consecutive
// ones by at most one swap in a Binary String
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the length of the
// longest consecutive 1's
int maximum_one(string s, int n)
{
    // To count all 1's in the string
    int cnt_one = 0;
 
    int max_cnt = 0, temp = 0;
 
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') {
            cnt_one++;
            temp++;
        }
        else {
            max_cnt = max(temp, max_cnt);
            temp = 0;
        }
    }
 
    max_cnt = max(max_cnt, temp);
 
    // To store cumulative 1's
    int left[n], right[n];
 
    if (s[0] == '1')
        left[0] = 1;
    else
        left[0] = 0;
 
    if (s[n - 1] == '1')
        right[n - 1] = 1;
    else
        right[n - 1] = 0;
 
    // Counting cumulative 1's from left
    for (int i = 1; i < n; i++) {
        if (s[i] == '1')
            left[i] = left[i - 1] + 1;
 
        // If 0 then start new cumulative
        // one from that i
        else
            left[i] = 0;
    }
 
    for (int i = n - 2; i >= 0; i--) {
        if (s[i] == '1')
            right[i] = right[i + 1] + 1;
 
        else
            right[i] = 0;
    }
 
    for (int i = 1; i < n - 1; i++) {
        // perform step 3 of the approach
        if (s[i] == '0') {
 
            // step 3
            int sum = left[i - 1] + right[i + 1];
 
            if (sum < cnt_one)
                max_cnt = max(max_cnt, sum + 1);
 
            else
                max_cnt = max(max_cnt, sum);
        }
    }
 
    return max_cnt;
}
 
// Driver Code
int main()
{
    // string
    string s = "111011101";
 
    cout << maximum_one(s, s.length());
 
    return 0;
}

Java

// Java  program to find length of longest consecutive
// ones by at most one swap in a Binary String
 
import java.io.*;
 
class GFG {
 
    // Function to calculate the length of the
    // longest consecutive 1's
    static int maximum_one(String s, int n)
    {
        // To count all 1's in the string
        int cnt_one = 0;
 
        int max_cnt = 0, temp = 0;
 
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '1') {
                cnt_one++;
                temp++;
            }
            else {
                max_cnt = Math.max(max_cnt, temp);
                temp = 0;
            }
        }
        max_cnt = Math.max(max_cnt, temp);
 
        // To store cumulative 1's
        int[] left = new int[n];
        int right[] = new int[n];
 
        if (s.charAt(0) == '1')
            left[0] = 1;
        else
            left[0] = 0;
 
        if (s.charAt(n - 1) == '1')
            right[n - 1] = 1;
        else
            right[n - 1] = 0;
 
        // Counting cumulative 1's from left
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == '1')
                left[i] = left[i - 1] + 1;
 
            // If 0 then start new cumulative
            // one from that i
            else
                left[i] = 0;
        }
 
        for (int i = n - 2; i >= 0; i--) {
            if (s.charAt(i) == '1')
                right[i] = right[i + 1] + 1;
 
            else
                right[i] = 0;
        }
 
        for (int i = 1; i < n - 1; i++) {
            // perform step 3 of the approach
            if (s.charAt(i) == '0') {
 
                // step 3
                int sum = left[i - 1] + right[i + 1];
 
                if (sum < cnt_one)
                    max_cnt = Math.max(max_cnt, sum + 1);
 
                else
                    max_cnt = Math.max(max_cnt, sum);
            }
        }
 
        return max_cnt;
    }
 
    // Driver Code
 
    public static void main(String[] args)
    {
        // string
        String s = "111011101";
 
        System.out.println(maximum_one(s, s.length()));
    }
}
// This code is contributed by anuj_67..

Python3

# Python 3 program to find length of
# longest consecutive ones by at most
# one swap in a Binary String
 
# Function to calculate the length
# of the longest consecutive 1's
 
 
def maximum_one(s, n):
 
    # To count all 1's in the string
    cnt_one = 0
 
    cnt, max_cnt = 0, 0
 
    for i in range(n):
        if (s[i] == '1'):
            cnt_one += 1
            cnt += 1
        else:
            max_cnt = max(max_cnt, cnt)
            cnt = 0
 
    max_cnt = max(max_cnt, cnt)
 
    # To store cumulative 1's
    left = [0] * n
    right = [0] * n
 
    if (s[0] == '1'):
        left[0] = 1
 
    else:
        left[0] = 0
 
    if (s[n - 1] == '1'):
        right[n - 1] = 1
 
    else:
        right[n - 1] = 0
 
    # Counting cumulative 1's from left
    for i in range(1, n):
        if (s[i] == '1'):
            left[i] = left[i - 1] + 1
 
        # If 0 then start new cumulative
        # one from that i
        else:
            left[i] = 0
 
    for i in range(n - 2, -1, -1):
 
        if (s[i] == '1'):
            right[i] = right[i + 1] + 1
 
        else:
            right[i] = 0
 
    for i in range(1, n-1):
 
        # perform step 3 of the approach
        if (s[i] == '0'):
 
            # step 3
            sum = left[i - 1] + right[i + 1]
 
            if (sum < cnt_one):
                max_cnt = max(max_cnt, sum+1)
 
            else:
                max_cnt = max(max_cnt, sum)
 
    return max_cnt
 
 
# Driver Code
if __name__ == "__main__":
 
    # string
    s = "111011101"
 
    print(maximum_one(s, len(s)))
 
# This code is contributed by Ryuga

C#

// C# program to find length of longest consecutive
// ones by at most one swap in a Binary String
using System;
 
class GFG {
 
    // Function to calculate the length of the
    // longest consecutive 1's
    static int maximum_one(string s, int n)
    {
        // To count all 1's in the string
        int cnt_one = 0;
 
        for (int i = 0; i < n; i++) {
            if (s[i] == '1')
                cnt_one++;
        }
 
        // To store cumulative 1's
        int[] left = new int[n];
        int[] right = new int[n];
 
        if (s[0] == '1')
            left[0] = 1;
        else
            left[0] = 0;
 
        if (s[n - 1] == '1')
            right[n - 1] = 1;
        else
            right[n - 1] = 0;
 
        // Counting cumulative 1's from left
        for (int i = 1; i < n; i++) {
            if (s[i] == '1')
                left[i] = left[i - 1] + 1;
 
            // If 0 then start new cumulative
            // one from that i
            else
                left[i] = 0;
        }
 
        for (int i = n - 2; i >= 0; i--) {
            if (s[i] == '1')
                right[i] = right[i + 1] + 1;
 
            else
                right[i] = 0;
        }
 
        int cnt = 0, max_cnt = 0;
 
        for (int i = 1; i < n - 1; i++) {
            // perform step 3 of the approach
            if (s[i] == '0') {
 
                // step 3
                int sum = left[i - 1] + right[i + 1];
 
                if (sum < cnt_one)
                    cnt = sum + 1;
 
                else
                    cnt = sum;
 
                max_cnt = Math.Max(max_cnt, cnt);
                cnt = 0;
            }
        }
 
        return max_cnt;
    }
 
    // Driver Code
 
    public static void Main()
    {
        // string
        string s = "111011101";
 
        Console.WriteLine(maximum_one(s, s.Length));
    }
}
// This code is contributed by inder_verma..

PHP

<?php
// PHP program to find length of longest
// consecutive ones by at most one swap
// in a Binary String
 
// Function to calculate the length
// of the longest consecutive 1's
function maximum_one($s, $n)
{
    // To count all 1's in the string
    $cnt_one = 0;
 
    for ($i = 0; $i < $n; $i++)
    {
        if ($s[$i] == '1')
            $cnt_one++;
    }
 
    // To store cumulative 1's
    // $left[$n]; $right[$n];
    if ($s[0] == '1')
        $left[0] = 1;
    else
        $left[0] = 0;
 
    if ($s[$n - 1] == '1')
        $right[$n - 1] = 1;
    else
        $right[$n - 1] = 0;
 
    // Counting cumulative 1's from left
    for ($i = 1; $i < $n; $i++)
    {
        if ($s[$i] == '1')
            $left[$i] = $left[$i - 1] + 1;
 
        // If 0 then start new cumulative
        // one from that i
        else
            $left[$i] = 0;
    }
 
    for ($i = $n - 2; $i >= 0; $i--)
    {
        if ($s[$i] == '1')
            $right[$i] = $right[$i + 1] + 1;
 
        else
            $right[$i] = 0;
    }
 
    $cnt = 0; $max_cnt = 0;
 
    for ($i = 1; $i < $n - 1; $i++)
    {
        // perform step 3 of the approach
        if ($s[$i] == '0')
        {
 
            // step 3
            $sum = $left[$i - 1] + $right[$i + 1];
 
            if ($sum < $cnt_one)
                $cnt = $sum + 1;
 
            else
                $cnt = $sum;
 
            $max_cnt = max($max_cnt, $cnt);
            $cnt = 0;
        }
    }
    return $max_cnt;
}
 
// Driver Code
 
// string
$s = "111011101";
 
echo maximum_one($s, strlen($s));
 
// This code is contributed
// by Akanksha Rai
?>

Javascript

<script>
 
// Javascript program to find length of longest consecutive
// ones by at most one swap in a Binary String
 
// Function to calculate the length of the
// longest consecutive 1's
function maximum_one(s, n)
{
    // To count all 1's in the string
    var cnt_one = 0;
     
    var max_cnt = 0, temp=0;
 
    for (var i = 0; i < n; i++)
    {
        if (s[i] == '1')
        {
            cnt_one++;
            temp++;
        }
        else
        {
            max_cnt = Math.max(temp,max_cnt);
            temp=0;
        }
    }
     
    max_cnt = Math.max(max_cnt, temp);
 
    // To store cumulative 1's
    var left = Array(n);
    var right = Array(n);
 
    if (s[0] == '1')
        left[0] = 1;
    else
        left[0] = 0;
 
    if (s[n - 1] == '1')
        right[n - 1] = 1;
    else
        right[n - 1] = 0;
 
    // Counting cumulative 1's from left
    for (var i = 1; i < n; i++) {
        if (s[i] == '1')
            left[i] = left[i - 1] + 1;
 
        // If 0 then start new cumulative
        // one from that i
        else
            left[i] = 0;
    }
 
    for (var i = n - 2; i >= 0; i--) {
        if (s[i] == '1')
            right[i] = right[i + 1] + 1;
 
        else
            right[i] = 0;
    }
 
 
    for (var i = 1; i < n - 1; i++) {
        // perform step 3 of the approach
        if (s[i] == '0') {
 
            // step 3
            var sum = left[i - 1] + right[i + 1];
 
            if (sum < cnt_one)
                max_cnt = Math.max(max_cnt, sum+1);
 
            else
                max_cnt = Math.max(max_cnt, sum);
 
        }
    }
 
    return max_cnt;
}
 
// Driver Code
// string
var s = "111011101";
document.write( maximum_one(s, s.length));
 
 
</script>
Producción: 

7

 

Complejidad de tiempo : O(N)
 

Publicación traducida automáticamente

Artículo escrito por Shashank_Pathak y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *