Dada la string str , la tarea es encontrar la longitud de la substring más larga de str de modo que no haya tres caracteres consecutivos iguales en la substring.
Ejemplos:
Entrada: str = “baaabbabbb”
Salida: 7
“aabbabb” es la substring requerida.
Entrada: str = “babba”
Salida: 5 La
string dada en sí misma es la substring más larga.
Enfoque: Se pueden seguir los siguientes pasos para resolver el problema:
- Si la longitud de la string dada es menor que 3 , entonces la longitud de la string será la respuesta.
- Inicialice temp y ans como 2 inicialmente, ya que esta es la longitud mínima de la substring más larga cuando la longitud de la string dada es mayor que 2 .
- Iterar en la string de 2 a N – 1 e incrementar la temperatura en 1 si str[i] != str[i – 1] o str[i] != str[i – 2] .
- De lo contrario, reinicialice temp = 2 y ans = max (ans, temp).
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 // longest substring such that no three // consecutive characters are same int maxLenSubStr(string& s) { // If the length of the given string // is less than 3 if (s.length() < 3) return s.length(); // Initialize temporary and final ans // to 2 as this is the minimum length // of substring when length of the given // string is greater than 2 int temp = 2; int ans = 2; // Traverse the string from the // third character to the last for (int i = 2; i < s.length(); i++) { // If no three consecutive characters // are same then increment temporary count if (s[i] != s[i - 1] || s[i] != s[i - 2]) temp++; // Else update the final ans and // reset the temporary count else { ans = max(temp, ans); temp = 2; } } ans = max(temp, ans); return ans; } // Driver code int main() { string s = "baaabbabbb"; cout << maxLenSubStr(s); return 0; }
Java
// Java implementation of the approach import java.util.*; class GFG { // Function to return the length of the // longest substring such that no three // consecutive characters are same static int maxLenSubStr(String s) { // If the length of the given string // is less than 3 if (s.length() < 3) return s.length(); // Initialize temporary and final ans // to 2 as this is the minimum length // of substring when length of the given // string is greater than 2 int temp = 2; int ans = 2; // Traverse the string from the // third character to the last for (int i = 2; i < s.length(); i++) { // If no three consecutive characters // are same then increment temporary count if (s.charAt(i) != s.charAt(i - 1) || s.charAt(i) != s.charAt(i - 2)) temp++; // Else update the final ans and // reset the temporary count else { ans = Math.max(temp, ans); temp = 2; } } ans = Math.max(temp, ans); return ans; } // Driver code public static void main(String[] args) { String s = "baaabbabbb"; System.out.println(maxLenSubStr(s)); } } // This code is contributed by PrinciRaj1992
Python3
# Python3 implementation of the approach # Function to return the length of the # longest substring such that no three # consecutive characters are same def maxLenSubStr(s): # If the length of the given string # is less than 3 if (len(s) < 3): return len(s) # Initialize temporary and final ans # to 2 as this is the minimum length # of substring when length of the given # string is greater than 2 temp = 2 ans = 2 # Traverse the string from the # third character to the last for i in range(2, len(s)): # If no three consecutive characters # are same then increment temporary count if (s[i] != s[i - 1] or s[i] != s[i - 2]): temp += 1 # Else update the final ans and # reset the temporary count else: ans = max(temp, ans) temp = 2 ans = max(temp, ans) return ans # Driver code s = "baaabbabbb" print(maxLenSubStr(s)) # This code is contributed by Mohit Kumar
C#
// C# implementation of the approach using System; class GFG { // Function to return the length of the // longest substring such that no three // consecutive characters are same static int maxLenSubStr(String s) { // If the length of the given string // is less than 3 if (s.Length < 3) return s.Length; // Initialize temporary and final ans // to 2 as this is the minimum length // of substring when length of the given // string is greater than 2 int temp = 2; int ans = 2; // Traverse the string from the // third character to the last for (int i = 2; i < s.Length; i++) { // If no three consecutive characters // are same then increment temporary count if (s[i] != s[i - 1] || s[i] != s[i - 2]) temp++; // Else update the final ans and // reset the temporary count else { ans = Math.Max(temp, ans); temp = 2; } } ans = Math.Max(temp, ans); return ans; } // Driver code static public void Main () { String s = "baaabbabbb"; Console.Write(maxLenSubStr(s)); } } // This code is contributed by ajit.
Javascript
<script> // Javascript implementation of the approach // Function to return the length of the // longest substring such that no three // consecutive characters are same function maxLenSubStr(s) { // If the length of the given string // is less than 3 if (s.length < 3) return s.length; // Initialize temporary and final ans // to 2 as this is the minimum length // of substring when length of the given // string is greater than 2 let temp = 2; let ans = 2; // Traverse the string from the // third character to the last for (let i = 2; i < s.length; i++) { // If no three consecutive characters // are same then increment temporary count if (s[i] != s[i - 1] || s[i] != s[i - 2]) temp++; // Else update the final ans and // reset the temporary count else { ans = Math.max(temp, ans); temp = 2; } } ans = Math.max(temp, ans); return ans; } let s = "baaabbabbb"; document.write(maxLenSubStr(s)); </script>
Producción:
7
Complejidad de tiempo: O(N) donde N es la longitud de la string.
Complejidad espacial: O(1)