Longitud de la substring más larga sin letras iguales consecutivas

Dada una string str , la tarea es encontrar la longitud de la substring más larga que no tiene ningún par de caracteres idénticos consecutivos. 
Ejemplos: 
 

Entrada: str = “abcdde” 
Salida:
“abcd” es la más larga
Entrada: str = “ccccdeededff” 
Salida:
“ededf” es la más larga 
 

Enfoque: Se pueden seguir los siguientes pasos para resolver el problema anterior: 
 

  • Inicialice cnt y maxi como 1 inicialmente, ya que esta es la respuesta mínima de la longitud de la respuesta más larga.
  • Iterar en la string de 1 a n – 1 e incrementar cnt en 1 si str[i] != str[i – 1] .
  • Si str[i] == str[i – 1] , reinicialice cnt como 1 y maxi a max(maxi, cnt) .

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

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the length
// of the required sub-string
int longestSubstring(string s)
{
    int cnt = 1;
    int maxi = 1;
 
    // Get the length of the string
    int n = s.length();
 
    // Iterate in the string
    for (int i = 1; i < n; i++) {
 
        // Check for not consecutive
        if (s[i] != s[i - 1])
            cnt++;
        else {
 
            // If cnt greater than maxi
            maxi = max(cnt, maxi);
 
            // Re-initialize
            cnt = 1;
        }
    }
 
    // Check after iteration
    // is complete
    maxi = max(cnt, maxi);
 
    return maxi;
}
 
// Driver code
int main()
{
    string s = "ccccdeededff";
    cout << longestSubstring(s);
 
    return 0;
}

Java

// Java implementation of the approach
import java.lang.Math;
 
class GfG
{
 
    // Function to return the length
    // of the required sub-string
    static int longestSubstring(String s)
    {
        int cnt = 1, maxi = 1;
     
        // Get the length of the string
        int n = s.length();
     
        // Iterate in the string
        for (int i = 1; i < n; i++)
        {
     
            // Check for not consecutive
            if (s.charAt(i) != s.charAt(i-1))
                cnt++;
            else
            {
     
                // If cnt greater than maxi
                maxi = Math.max(cnt, maxi);
     
                // Re-initialize
                cnt = 1;
            }
        }
     
        // Check after iteration is complete
        maxi = Math.max(cnt, maxi);
     
        return maxi;
    }
 
    // Driver code
    public static void main(String []args)
    {
         
        String s = "ccccdeededff";
        System.out.println(longestSubstring(s));
    }
}
 
// This code is contributed by Rituraj Jain

C#

// C# implementation of the approach
using System;
 
class GfG
{
 
    // Function to return the length
    // of the required sub-string
    static int longestSubstring(string s)
    {
        int cnt = 1, maxi = 1;
     
        // Get the length of the string
        int n = s.Length;
     
        // Iterate in the string
        for (int i = 1; i < n; i++)
        {
     
            // Check for not consecutive
            if (s[i] != s[i - 1])
                cnt++;
            else
            {
     
                // If cnt greater than maxi
                maxi = Math.Max(cnt, maxi);
     
                // Re-initialize
                cnt = 1;
            }
        }
     
        // Check after iteration is complete
        maxi = Math.Max(cnt, maxi);
     
        return maxi;
    }
 
    // Driver code
    static void Main()
    {
         
        string s = "ccccdeededff";
        Console.WriteLine(longestSubstring(s));
    }
}
 
// This code is contributed by mits

Python3

# Python3 implementation of the approach
 
# Function to return the length
# of the required sub-string
def longestSubstring(s) :
 
    cnt = 1;
    maxi = 1;
 
    # Get the length of the string
    n = len(s);
 
    # Iterate in the string
    for i in range(1, n) :
 
        # Check for not consecutive
        if (s[i] != s[i - 1]) :
            cnt += 1;
             
        else :
             
            # If cnt greater than maxi
            maxi = max(cnt, maxi);
 
            # Re-initialize
            cnt = 1;
 
    # Check after iteration
    # is complete
    maxi = max(cnt, maxi);
 
    return maxi;
 
# Driver code
if __name__ == "__main__" :
     
    s = "ccccdeededff";
    print(longestSubstring(s));
     
# This code is contributed by Ryuga

PHP

<?php
// PHP implementation of the approach
 
// Function to return the length
// of the required sub-string
function longestSubstring($s)
{
    $cnt = 1;
    $maxi = 1;
 
    // Get the length of the string
    $n = strlen($s);
 
    // Iterate in the string
    for ($i = 1; $i < $n; $i++)
    {
 
        // Check for not consecutive
        if ($s[$i] != $s[$i - 1])
            $cnt++;
        else
        {
 
            // If cnt greater than maxi
            $maxi = max($cnt, $maxi);
 
            // Re-initialize
            $cnt = 1;
        }
    }
 
    // Check after iteration
    // is complete
    $maxi = max($cnt, $maxi);
 
    return $maxi;
}
 
// Driver code
$s = "ccccdeededff";
echo longestSubstring($s);
 
// This code is contributed by Akanksha Rai
?>

Javascript

<script>
// javascript implementation of the approach class GfG
 
// Function to return the length
// of the required sub-string
function longestSubstring(s)
{
    var cnt = 1, maxi = 1;
 
    // Get the length of the string
    var n = s.length;
 
    // Iterate in the string
    for (i = 1; i < n; i++)
    {
 
        // Check for not consecutive
        if (s.charAt(i) != s.charAt(i-1))
            cnt++;
        else
        {
 
            // If cnt greater than maxi
            maxi = Math.max(cnt, maxi);
 
            // Re-initialize
            cnt = 1;
        }
    }
 
    // Check after iteration is complete
    maxi = Math.max(cnt, maxi);
 
    return maxi;
}
 
// Driver code
var s = "ccccdeededff";
document.write(longestSubstring(s));
 
 
// This code contributed by shikhasingrajput
</script>
Producción: 

5

 

Complejidad temporal: O(n)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por Striver 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 *