Dada una string S que consta de N caracteres y un número entero positivo K , la tarea es verificar si existe alguna string (K + 1) , es decir, A 1 , A 2 , A 3 , …, A K , A (K + 1) tal que la concatenación de las strings A 1 , A 2 , A 3 , …, A K y A (K + 1) y la concatenación del reverso de cada string A K ,A (K – 1) , A (K – 2) , …, A 1 y A 0 es la string S . Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada: S = “qwqwq”, K = 1
Salida: Sí
Explicación:
Considere la string A 1 como “qw” y A 2 como “q”. Ahora la concatenación de A 1 , A 2 , inversa de A 1 es “qwqwq”, que es lo mismo que la string S dada.Entrada: S = “qwqwa”, K = 2
Salida: No
Enfoque: El problema dado se puede resolver basándose en la observación de que para que una string S satisfaga la condición dada, los primeros K caracteres deben ser iguales a los últimos K caracteres de la string dada. Siga los pasos a continuación para resolver el problema:
- Si el valor de ( 2*K + 1) es mayor que N , imprima «No» y regrese de la función .
- De lo contrario, almacene el prefijo de tamaño K , es decir, S[0, …, K] en una string A , y el sufijo de tamaño K , es decir, S[N – K, …, N – 1] en una string B.
- Invierta la string B y verifique si A es igual a B o no. Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .
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 check if the string S
// can be obtained by (K + 1) non-empty
// substrings whose concatenation and
// concatenation of the reverse
// of these K strings
void checkString(string s, int k)
{
// Stores the size of the string
int n = s.size();
// If n is less than 2*k+1
if (2 * k + 1 > n) {
cout << "No";
return;
}
// Stores the first K characters
string a = s.substr(0, k);
// Stores the last K characters
string b = s.substr(n - k, k);
// Reverse the string
reverse(b.begin(), b.end());
// If both the strings are equal
if (a == b)
cout << "Yes";
else
cout << "No";
}
// Driver Code
int main()
{
string S = "qwqwq";
int K = 1;
checkString(S, K);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG
{
// Function to check if the string S
// can be obtained by (K + 1) non-empty
// substrings whose concatenation and
// concatenation of the reverse
// of these K strings
static void checkString(String s, int k)
{
// Stores the size of the string
int n = s.length();
// If n is less than 2*k+1
if (2 * k + 1 > n) {
System.out.println("No");
return;
}
// Stores the first K characters
String a = s.substring(0, k);
// Stores the last K characters
String b = s.substring(n - k, n);
// Reverse the string
StringBuffer str = new StringBuffer(b);
// To reverse the string
str.reverse();
b = str.toString();
// If both the strings are equal
if (a.equals(b))
System.out.println("Yes");
else
System.out.println("No");
}
// Driver Code
public static void main (String[] args)
{
String S = "qwqwq";
int K = 1;
checkString(S, K);
}
}
// This code is contributed by Dharanendra L V.
Python3
# Python3 program for the above approach
# Function to check if the S
# can be obtained by (K + 1) non-empty
# substrings whose concatenation and
# concatenation of the reverse
# of these K strings
def checkString(s, k):
# Stores the size of the string
n = len(s)
# If n is less than 2*k+1
if (2 * k + 1 > n):
print("No")
return
# Stores the first K characters
a = s[0:k]
# Stores the last K characters
b = s[n - k:n]
# Reverse the string
b = b[::-1]
# If both the strings are equal
if (a == b):
print("Yes")
else:
print("No")
# Driver Code
if __name__ == '__main__':
S = "qwqwq"
K = 1
checkString(S, K)
# This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
class GFG {
// Function to check if the string S
// can be obtained by (K + 1) non-empty
// substrings whose concatenation and
// concatenation of the reverse
// of these K strings
static void checkString(string s, int k)
{
// Stores the size of the string
int n = s.Length;
// If n is less than 2*k+1
if (2 * k + 1 > n) {
Console.Write("No");
return;
}
// Stores the first K characters
string a = s.Substring(0, k);
// Stores the last K characters
string b = s.Substring(n - k, k);
// Reverse the string
char[] arr = b.ToCharArray();
Array.Reverse(arr);
b = new String(arr);
// If both the strings are equal
if (a == b)
Console.Write("Yes");
else
Console.Write("No");
}
// Driver Code
public static void Main()
{
string S = "qwqwq";
int K = 1;
checkString(S, K);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// Javascript program for the above approach
// Function to check if the string S
// can be obtained by (K + 1) non-empty
// substrings whose concatenation and
// concatenation of the reverse
// of these K strings
function checkString(s, k)
{
// Stores the size of the string
let n = s.length;
// If n is less than 2*k+1
if (2 * k + 1 > n) {
document.write("No");
return;
}
// Stores the first K characters
let a = s.substr(0, k);
// Stores the last K characters
let b = s.substr(n - k, k);
// Reverse the string
b.split("").reverse().join("")
// If both the strings are equal
if (a == b)
document.write("Yes");
else
document.write("No");
}
// Driver Code
let S = "qwqwq";
let K = 1;
checkString(S, K);
// This code is contributed by gfgking.
</script>
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por shreyajaiswal3 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA