Dada una string S , la tarea es encontrar la longitud de la substring más larga entre cualquier par de ocurrencias del mismo carácter.
Ejemplos:
Entrada: S = “accabacc”
Salida: 6
Explicación: La substring más larga que cumple las condiciones requeridas es “cabbac”, que se encuentra entre S[1](= ‘c’) y s[8](= ‘c’).Entrada: S = “aab”
Salida: 0
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice dos variables res y diff para almacenar la longitud de la substring más larga y la longitud de la substring actual entre pares de los mismos caracteres, respectivamente.
- Iterar sobre los caracteres de la string de izquierda a derecha.
- Iterar sobre la string restante a la derecha, de derecha a izquierda hasta el carácter actual.
- Si se obtienen dos caracteres iguales, es decir, S[i] = S[j], , almacene la longitud de la substring entre ellos en diff .
- Actualice el valor de res como max(res, diff). para que res almacene la substring más larga del tipo requerido obtenida hasta el momento.
- Después de completar el recorrido de la string, imprima res como la respuesta requerida.
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 find the longest substring
// between pair of repetitions of the same character
int longestbetweenequalcharacters(string S)
{
// Length of the string
int n = S.length();
// Stores the maximum length and
// length of current substring
// satisfying given conditions
int res = -1, diff = -1;
// Traverse the string
for (int i = 0; i < n - 1; i++) {
// Search for repetition of S[i]
for (int j = n - 1; j > i; j--) {
// If repetition occurs
if (S[i] == S[j]) {
// Store the length of
// the substring
diff = j - i - 1;
// Update maximum length of
// substring obtained
res = max(diff, res);
}
}
}
// Return obtained maximum length
return res;
}
// Driver Code
int main()
{
string s = "accabbacc";
cout << longestbetweenequalcharacters(s);
}
Java
// Java program to implement
// the above approach
class GFG{
// Function to find the longest substring
// between pair of repetitions of the
// same character
static int longestbetweenequalcharacters(String S)
{
// Length of the string
int n = S.length();
// Stores the maximum length and
// length of current substring
// satisfying given conditions
int res = -1, diff = -1;
// Traverse the string
for(int i = 0; i < n - 1; i++)
{
// Search for repetition of S[i]
for(int j = n - 1; j > i; j--)
{
// If repetition occurs
if (S.charAt(i) == S.charAt(j))
{
// Store the length of
// the substring
diff = j - i - 1;
// Update maximum length of
// substring obtained
res = Math.max(diff, res);
}
}
}
// Return obtained maximum length
return res;
}
// Driver code
public static void main(String[] args)
{
String s = "accabbacc";
System.out.println(
longestbetweenequalcharacters(s));
}
}
// This code is contributed by code_hunt
Python3
# Python3 program to implement # the above approach # Function to find the longest # substring between pair of # repetitions of the same character def longestbetweenequalcharacters(S): # Length of the string n = len(S) # Stores the maximum length and # length of current substring # satisfying given conditions res = -1 diff = -1 # Traverse the string for i in range(n - 1): # Search for repetition of S[i] for j in range(n - 1, i, -1): # If repetition occurs if (S[i] == S[j]): # Store the length of # the substring diff = j - i - 1 # Update maximum length of # substring obtained res = max(diff, res) # Return obtained maximum length return res # Driver Code if __name__ == '__main__': s = "accabbacc" print(longestbetweenequalcharacters(s)) # This code is contributed by doreamon_
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to find the longest substring
// between pair of repetitions of the
// same character
static int longestbetweenequalcharacters(String S)
{
// Length of the string
int n = S.Length;
// Stores the maximum length and
// length of current substring
// satisfying given conditions
int res = -1, diff = -1;
// Traverse the string
for(int i = 0; i < n - 1; i++)
{
// Search for repetition of S[i]
for(int j = n - 1; j > i; j--)
{
// If repetition occurs
if (S[i] == S[j])
{
// Store the length of
// the substring
diff = j - i - 1;
// Update maximum length of
// substring obtained
res = Math.Max(diff, res);
}
}
}
// Return obtained maximum length
return res;
}
// Driver code
public static void Main()
{
string s = "accabbacc";
Console.WriteLine(
longestbetweenequalcharacters(s));
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// javascript program to implement
// the above approach
// Function to find the longest substring
// between pair of repetitions of the
// same character
function longestbetweenequalcharacters(S)
{
// Length of the string
var n = S.length;
// Stores the maximum length and
// length of current substring
// satisfying given conditions
var res = -1, diff = -1;
// Traverse the string
for(i = 0; i < n - 1; i++)
{
// Search for repetition of S[i]
for(j = n - 1; j > i; j--)
{
// If repetition occurs
if (S.charAt(i) == S.charAt(j))
{
// Store the length of
// the substring
diff = j - i - 1;
// Update maximum length of
// substring obtained
res = Math.max(diff, res);
}
}
}
// Return obtained maximum length
return res;
}
// Driver code
var s = "accabbacc";
document.write(
longestbetweenequalcharacters(s));
// This code contributed by shikhasingrajput
</script>
Producción:
6
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por IshwarGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA