Encuentre el tiempo que tarda la señal en llegar a todas las posiciones en una string

Dada una string de ‘x’ y ‘o’. De cada ‘x’ se origina una señal que viaja en ambas direcciones. La señal tarda una unidad de tiempo en viajar a la siguiente celda. Si una celda contiene ‘o’, la señal la cambia a ‘x’. La tarea es calcular el tiempo necesario para convertir la array en una string de señales. 
Una string de señal contiene solo ‘x’.
Ejemplos: 
 

Entrada: s = “oooxooooxooo” 
Salida: 3
Entrada: s = “oooxoooooo” 
Salida: 4 
 

Fuente : OYO Rooms Interview Set 2
La idea es encontrar la longitud de la ‘o’ contigua más larga. También verifique, si ‘x’ está presente en el lado derecho e izquierdo de ‘o’ contiguas, entonces el período de tiempo se reducirá a la mitad de la duración máxima; de lo contrario, el período de tiempo será igual a la duración máxima.
A continuación se muestra la implementación del enfoque anterior. 
 

// C++ program to Find time taken for signal
// to reach all positions in a string
#include <bits/stdc++.h>
using namespace std;
 
// Returns time needed for signal to traverse
// through complete string.
int maxLength(string s, int n)
{
    int right = 0, left = 0;
    int coun = 0, max_length = INT_MIN;
 
    s = s + '1'; // for the calculation of last index
    // for strings like oxoooo, xoxxoooo ..
 
    for (int i = 0; i <= n; i++) {
        if (s[i] == 'o')
            coun++;
 
        else {
 
            // if coun is greater than max_length
            if (coun > max_length) {
 
                right = 0;
                left = 0;
 
                // if 'x' is present at the right side
                // of max_length
                if (s[i] == 'x')
                    right = 1;
 
                // if 'x' is present at left side of
                // max_length
                if (((i - coun) > 0) && (s[i - coun - 1] == 'x'))
                    left = 1;
 
                // We use ceiling function to handle odd
                // number 'o's
                coun = ceil((double)coun / (right + left));
 
                max_length = max(max_length, coun);
            }
            coun = 0;
        }
    }
 
    return max_length;
}
 
// Driver code
int main()
{
    string s = "oooxoooooooooxooo";
    int n = s.size();
    cout << maxLength(s, n);
    return 0;
}

// Java program to Find time taken for signal
// to reach all positions in a string
public class GFG {
 
    // Returns time needed for signal to traverse
    // through complete string.
    static int maxLength(String s, int n)
    {
        int right = 0, left = 0;
        int coun = 0, max_length = Integer.MIN_VALUE;
 
        s = s + '1'; // for the calculation of last index
        // for strings like oxoooo, xoxxoooo ..
 
        for (int i = 0; i <= n; i++) {
            if (s.charAt(i) == 'o')
                coun++;
 
            else {
 
                // if coun is greater than max_length
                if (coun > max_length) {
 
                    right = 0;
                    left = 0;
 
                    // if 'x' is present at the right side
                    // of max_length
                    if (s.charAt(i) == 'x')
                        right = 1;
 
                    // if 'x' is present at left side of
                    // max_length
                    if (((i - coun) > 0) && (s.charAt(i - coun - 1) == 'x'))
                        left = 1;
 
                    // We use ceiling function to handle odd
                    // number 'o's
                    coun = (int)Math.ceil((double)coun / (right + left));
 
                    max_length = Math.max(max_length, coun);
                }
                coun = 0;
            }
        }
 
        return max_length;
    }
 
    // Driver code
    public static void main(String args[])
    {
        String s = "oooxoooooooooxooo";
        int n = s.length();
        System.out.println(maxLength(s, n));
    }
    // This code is contributed by ANKITRAI1
}

# Python3 program to Find time taken for signal
# to reach all positions in a string
import sys
import math
 
# Returns time needed for signal
# to traverse through complete string.
def maxLength(s, n):
    right = 0
    left = 0
    coun = 0
    max_length = -(sys.maxsize-1)
     
    # for the calculation of last index
    s = s+'1'
     
    # for strings like oxoooo, xoxxoooo 
    for i in range(0, n + 1):
        if s[i]=='o':
            coun+= 1
        else:
             
            # if coun is greater than
            # max_length
            if coun>max_length:
                right = 0
                left = 0
                 
                # if 'x' is present at the right side
                # of max_length
                if s[i]=='x':
                    right = 1
                     
                # if 'x' is present at left side of
                # max_length
                if i-coun>0 and s[i-coun-1] == 'x':
                    left = 1
                     
                # We use ceiling function to handle odd
                # number 'o's
                coun = math.ceil(float(coun/(right + left)))
                max_length = max(max_length, coun)
            coun = 0
 
    return max_length
 
# Driver code
if __name__=='__main__':
    s = "oooxoooooooooxooo"
    n = len(s)
    print(maxLength(s, n))
 
# This code is contributed by
# Shrikant13

// C# program to Find time taken
// for signal to reach all
// positions in a string
using System;
 
class GFG {
 
    // Returns time needed for signal
    // to traverse through complete string.
    static int maxLength(string s, int n)
    {
        int right = 0, left = 0;
        int coun = 0, max_length = int.MinValue;
 
        s = s + '1'; // for the calculation of last index
 
        // for strings like oxoooo, xoxxoooo ..
        for (int i = 0; i <= n; i++) {
            if (s[i] == 'o')
                coun++;
 
            else {
 
                // if coun is greater than max_length
                if (coun > max_length) {
                    right = 0;
                    left = 0;
 
                    // if 'x' is present at the right
                    // side of max_length
                    if (s[i] == 'x')
                        right = 1;
 
                    // if 'x' is present at left side
                    // of max_length
                    if (((i - coun) > 0) && (s[i - coun - 1] == 'x'))
                        left = 1;
 
                    // We use ceiling function to
                    // handle odd number 'o's
                    coun = (int)Math.Ceiling((double)coun / (right + left));
 
                    max_length = Math.Max(max_length, coun);
                }
                coun = 0;
            }
        }
 
        return max_length;
    }
 
    // Driver code
    public static void Main()
    {
        string s = "oooxoooooooooxooo";
        int n = s.Length;
        Console.Write(maxLength(s, n));
    }
}
 
// This code is contributed
// by ChitraNayal

<?php
// PHP program to Find time taken for signal
// to reach all positions in a string
 
// Returns time needed for signal
// to traverse through complete string.
function maxLength($s, $n)
{
    $right = 0; $left = 0;
    $coun = 0;
    $max_length = PHP_INT_MIN;
 
    $s = $s . '1'; // for the calculation of last index
                   // for strings like oxoooo, xoxxoooo ..
 
    for ($i = 0; $i <= $n; $i++)
    {
        if ($s[$i] == 'o')
            $coun++;
 
        else
        {
 
            // if coun is greater than max_length
            if ($coun > $max_length)
            {
 
                $right = 0;
                $left = 0;
 
                // if 'x' is present at the right side
                // of max_length
                if ($s[$i] == 'x')
                    $right = 1;
 
                // if 'x' is present at left side of
                // max_length
                if ((($i - $coun) > 0) &&
                    ($s[$i - $coun - 1] == 'x'))
                    $left = 1;
 
                // We use ceiling function to handle odd
                // number 'o's
                $coun = (int)ceil((double)$coun / ($right +
                                                   $left));
 
                $max_length = max($max_length, $coun);
            }
            $coun = 0;
        }
    }
 
    return $max_length;
}
 
// Driver code
$s = "oooxoooooooooxooo";
$n = strlen($s);
echo(maxLength($s, $n));
 
// This code is contributed by Code_Mech

<script>
// Javascript program to Find time taken for signal
// to reach all positions in a string
 
 
// Returns time needed for signal to traverse
// through complete string.
function maxLength( s, n)
{
    var right = 0, left = 0;
    var coun = 0, max_length = Number.MIN_VALUE;
 
    s = s + '1'; // for the calculation of last index
    // for strings like oxoooo, xoxxoooo ..
 
    for (var i = 0; i <= n; i++) {
        if (s[i] == 'o')
            coun++;
 
        else {
 
            // if coun is greater than max_length
            if (coun > max_length) {
 
                right = 0;
                left = 0;
 
                // if 'x' is present at the right side
                // of max_length
                if (s[i] == 'x')
                    right = 1;
 
                // if 'x' is present at left side of
                // max_length
                if (((i - coun) > 0) && (s[i - coun - 1] == 'x'))
                    left = 1;
 
                // We use ceiling function to handle odd
                // number 'o's
                coun = Math.ceil(coun / (right + left));
 
                max_length = Math.max(max_length, coun);
            }
            coun = 0;
        }
    }
 
    return max_length;
}
 
var s = "oooxoooooooooxooo";
var n = s.length;
document.write( maxLength(s, n));
         
// This code is contributed by SoumikMondal
</script>

5