Dada una string S que consta de N caracteres, la tarea es verificar si esta string tiene una substring igual reversible desde el principio y el final. En caso afirmativo, imprima True y luego la substring más larga presente siguiendo las condiciones dadas; de lo contrario, imprima False.
Ejemplo:
Entrada: S = “abca”
Salida:
Verdadero
a
Explicación:
La substring “a” es solo la substring más larga que satisface los criterios dados. Por lo tanto, imprime a.Entrada: S = “acdfbcdca”
Salida:
Verdadero
acd
Explicación:
La substring “acd” es solo la substring más larga que satisface los criterios dados. Por lo tanto, imprima acd.Entrada: S = “abcdcb”
Salida: Falso
Enfoque: El problema dado se puede resolver utilizando el enfoque de dos punteros . Siguiendo los pasos a continuación para resolver el problema dado:
- Inicialice una string, digamos ans como «» que almacena la string resultante que satisface los criterios dados.
- Inicialice dos variables, digamos i y j como 0 y (N – 1) respectivamente.
- Itere un ciclo hasta que j no sea negativo y f los caracteres S[i] y S[j] sean iguales, luego simplemente agregue el carácter S[i] en la variable ans e incremente el valor de i en 1 y disminuya el valor de j por 1 . De lo contrario, rompa el bucle .
- Después de completar los pasos anteriores, si la string ans está vacía, imprima Falso . De lo contrario, imprima True y luego imprima la string ans como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print longest substring
// that appears at beginning of string
// and also at end in reverse order
void commonSubstring(string s)
{
int n = s.size();
int i = 0;
int j = n - 1;
// Stores the resultant string
string ans = "";
while (j >= 0) {
// If the characters are same
if (s[i] == s[j]) {
ans += s[i];
i++;
j--;
}
// Otherwise, break
else {
break;
}
}
// If the string can't be formed
if (ans.size() == 0)
cout << "False";
// Otherwise print resultant string
else {
cout << "True \n"
<< ans;
}
}
// Driver Code
int main()
{
string S = "abca";
commonSubstring(S);
return 0;
}
Java
// Java program for the above approach
public class GFG
{
// Function to print longest substring
// that appears at beginning of string
// and also at end in reverse order
static void commonSubstring(String s)
{
int n = s.length();
int i = 0;
int j = n - 1;
// Stores the resultant string
String ans = "";
while (j >= 0) {
// If the characters are same
if (s.charAt(i) == s.charAt(j)) {
ans += s.charAt(i);
i++;
j--;
}
// Otherwise, break
else {
break;
}
}
// If the string can't be formed
if (ans.length() == 0)
System.out.println("False");
// Otherwise print resultant string
else {
System.out.println("True ");
System.out.println(ans);
}
}
// Driver Code
public static void main(String []args)
{
String S = "abca";
commonSubstring(S);
}
}
// This code is contributed by AnkThon
Python3
# python program for the above approach
# Function to print longest substring
# that appears at beginning of string
# and also at end in reverse order
def commonSubstring(s):
n = len(s)
i = 0
j = n - 1
# Stores the resultant string
ans = ""
while (j >= 0):
# // If the characters are same
if (s[i] == s[j]):
ans += s[i]
i = i + 1
j = j - 1
# Otherwise, break
else:
break
# If the string can't be formed
if (len(ans) == 0):
print("False")
# Otherwise print resultant string
else:
print("True")
print(ans)
# Driver Code
if __name__ == "__main__":
S = "abca"
commonSubstring(S)
# This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
class GFG
{
// Function to print longest substring
// that appears at beginning of string
// and also at end in reverse order
static void commonSubstring(string s)
{
int n = s.Length;
int i = 0;
int j = n - 1;
// Stores the resultant string
string ans = "";
while (j >= 0) {
// If the characters are same
if (s[i] == s[j]) {
ans += s[i];
i++;
j--;
}
// Otherwise, break
else {
break;
}
}
// If the string can't be formed
if (ans.Length == 0)
Console.WriteLine("False");
// Otherwise print resultant string
else {
Console.WriteLine("True ");
Console.WriteLine(ans);
}
}
// Driver Code
public static void Main()
{
string S = "abca";
commonSubstring(S);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to print longest substring
// that appears at beginning of string
// and also at end in reverse order
function commonSubstring(s) {
let n = s.length;
let i = 0;
let j = n - 1;
// Stores the resultant string
let ans = "";
while (j >= 0) {
// If the characters are same
if (s[i] == s[j]) {
ans += s[i];
i++;
j--;
}
// Otherwise, break
else {
break;
}
}
// If the string can't be formed
if (ans.length == 0)
document.write("False");
// Otherwise print resultant string
else {
document.write("True" + "<br>"
+ ans);
}
}
// Driver Code
let S = "abca";
commonSubstring(S);
// This code is contributed by Potta Lokesh
</script>
Producción
a
Complejidad temporal: O(N)
Espacio auxiliar: O(1)