Dada una string S. Encuentre la substring más larga que comienza con el carácter C1 , termina con el carácter C3 y tiene al menos un carácter C2 en el medio. Imprima «-1» si no existe tal substring.
Nota: Las letras mayúsculas y minúsculas se tratan de manera diferente, por lo que ‘a’ y ‘A’ no son equivalentes.
Ejemplos:
Entrada: S = “aasdfdsafsdasf”, C1 = ‘d’, C2 = ‘s’, C3 = ‘d’
Salida: 8 dfdsafsd
Explicación: “dfdsafsd” comienza con ‘d’ y termina con ‘d’ y dos ‘s’ entre.Entrada: S = «GeeksForGeeks», C1 = ‘G’, C2 = ‘e’, C3 = ‘k’
Salida: 12 GeeksForGeek
Explicación: «GeeksForGeek» comienza con ‘G’ y termina con ‘k’ y cuatro ‘e’ entre.Entrada: S = “Profecía”, C1 = ‘p’, C2 = ‘p’, C3 = ‘t’
Salida: -1
Explicación: No existe ninguna substring cuyo carácter inicial sea ‘p’ y finalice como ‘p’.
Enfoque: El problema se puede resolver usando la siguiente idea:
Encuentre la primera aparición de C1 y la última aparición de C3. Si hay algún C2 entre ellos, entonces esta es la substring más larga posible. De lo contrario, no es posible tal substring.
Siga los pasos que se mencionan a continuación para resolver el problema:
- Encuentre la primera aparición de C1 en S (digamos i ).
- Comience a iterar desde i hasta el final de la string:
- Agregue el carácter a la substring más larga.
- Si algún carácter es igual a C2 , incremente el conteo de C2 .
- Si se encuentra C3 y el recuento de C2 no es cero, actualice la substring más larga.
- Si la cuenta es 0, devuelve -1.
- De lo contrario, devuelva la substring formada hasta la última aparición de C3 .
A continuación se muestra la implementación del enfoque anterior.
C++14
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the longest substring
string Solve(string& S, char& C1,
char& C2, char& C3)
{
int maxLen = 0, countB = 0,
i, j, n = S.length();
// First occurrence of C1
for (i = 0; i < n; i++) {
if (S[i] == C1) {
j = i;
break;
}
}
// Finding the longest substring
while (j++ < n) {
if (S[j] == C2)
countB++;
if (countB > 0 && S[j] == C3)
maxLen = max(maxLen, j - i + 1);
}
if (maxLen == 0)
return "-1";
return S.substr(i, maxLen);
}
// Driver code
int main()
{
string S = "GeeksForGeeks";
char C1 = 'G';
char C2 = 'e';
char C3 = 'k';
string ans = Solve(S, C1, C2, C3);
if (ans.compare("-1") == 0)
cout << "-1";
else
cout << ans.length() << " "
<< ans;
return 0;
}
Java
// Java code to implement the approach
public class GFG
{
// Function to find the longest substring
static String Solve(String S, char C1, char C2, char C3)
{
int maxLen = 0;
int countB = 0;
int i, j = 0;
int n = S.length();
// First occurrence of C1
for (i = 0; i < n; i++) {
if (S.charAt(i) == C1) {
j = i;
break;
}
}
// Finding the longest substring
while (++j < n) {
if (S.charAt(j) == C2)
countB++;
if (countB > 0 && S.charAt(j) == C3)
maxLen = Math.max(maxLen, j - i + 1);
}
if (maxLen == 0)
return "-1";
return S.substring(i, maxLen);
}
// Driver code
public static void main(String[] args)
{
String S = "GeeksForGeeks";
char C1 = 'G';
char C2 = 'e';
char C3 = 'k';
String ans = Solve(S, C1, C2, C3);
if (ans == "-1")
System.out.println("-1");
else
System.out.println(ans.length() + " " + ans);
}
}
//This code is contributed by phasing17
Python3
# Python 3 code to implement the approach
# Function to find the longest substrin
def Solve(S, C1,
C2, C3):
maxLen = 0
countB = 0
n = len(S)
# First occurrence of C1
for i in range(n):
if (S[i] == C1):
j = i
break
# Finding the longest substring
while (j < n):
if (S[j] == C2):
countB += 1
if (countB > 0 and S[j] == C3):
maxLen = max(maxLen, j - i + 1)
j += 1
if (maxLen == 0):
return "-1"
return S[i: maxLen]
# Driver code
if __name__ == "__main__":
S = "GeeksForGeeks"
C1 = 'G'
C2 = 'e'
C3 = 'k'
ans = Solve(S, C1, C2, C3)
if (ans == "-1"):
print("-1")
else:
print(len(ans), ans)
# This code is contributed by ukasp.
C#
// C# code to implement the approach
using System;
class GeeksForGeeks {
// Function to find the longest substring
static string Solve(string S, char C1, char C2, char C3)
{
int maxLen = 0, countB = 0, i = 0, j = 0,
n = S.Length;
// First occurrence of C1
for (i = 0; i < n; i++) {
if (S[i] == C1) {
j = i;
break;
}
}
// Finding the longest substring
while (j < n) {
if (S[j] == C2)
countB++;
if (countB > 0 && S[j] == C3)
maxLen = Math.Max(maxLen, j - i + 1);
j++;
}
if (maxLen == 0)
return "-1";
return S.Substring(i, maxLen);
}
// Driver code
public static void Main()
{
string S = "GeeksForGeeks";
char C1 = 'G';
char C2 = 'e';
char C3 = 'k';
string ans = Solve(S, C1, C2, C3);
if (ans == "-1")
Console.Write("-1");
else
Console.Write(ans.Length + " " + ans);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
// Function to find the longest substring
function Solve(S, C1,
C2, C3)
{
let maxLen = 0, countB = 0,
i, j, n = S.length;
// First occurrence of C1
for (i = 0; i < n; i++) {
if (S[i] == C1) {
j = i;
break;
}
}
// Finding the longest substring
while (j++ < n) {
if (S[j] == C2)
countB++;
if (countB > 0 && S[j] == C3)
maxLen = Math.max(maxLen, j - i + 1);
}
if (maxLen == 0)
return "-1";
return S.slice(i, maxLen);
}
// Driver code
let S = "GeeksForGeeks";
let C1 = 'G';
let C2 = 'e';
let C3 = 'k';
let ans = Solve(S, C1, C2, C3);
if (ans=="-1")
document.write( "-1");
else
document.write(ans.length + " " + ans)
// This code is contributed by Potta Lokesh
</script>
12 GeeksForGeek
Complejidad de tiempo: O(N), donde N es la longitud de la string
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por prophet1999 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA