Bei einer gegebenen Zeichenfolge S , die aus N Zeichen und einer positiven ganzen Zahl K besteht, besteht die Aufgabe darin, zu prüfen, ob es irgendwelche (K + 1) Zeichenfolgen gibt, dh A ₁ , A ₂ , A ₃ , …, A _K , A _{(K + 1)} so dass die Verkettung der Zeichenfolgen   A ₁ , A ₂ , A ₃ , …, A _K und A _{(K + 1)} und die Verkettung der Umkehrung jeder Zeichenfolge A _K ,A _{(K – 1)} , A _{(K – 2)} , …, A ₁ und A ₀ ist die Zeichenfolge S . Wenn dies zutrifft, geben Sie „Ja“ aus . Geben Sie andernfalls „Nein“ aus .

Beispiele:

Eingabe: S = „qwqwq“, K = 1
Ausgabe: Ja
Erklärung:
Betrachten Sie die Zeichenkette A ₁ als „qw“ und A ₂ als „q“. Nun ist die Verkettung von   A ₁ , A ₂ , Umkehrung von   A ₁ „qwqwq“, was der gegebenen Zeichenfolge S entspricht.

Eingabe: S = „qwqwa“, K = 2
Ausgabe: Nein

Ansatz: Das gegebene Problem kann basierend auf der Beobachtung gelöst werden, dass für einen String S , um die gegebene Bedingung zu erfüllen, die ersten K Zeichen gleich den letzten K Zeichen des gegebenen Strings sein müssen. Führen Sie die folgenden Schritte aus, um das Problem zu lösen:

• Wenn der Wert von ( 2*K + 1) größer als N ist, geben Sie „Nein“ aus und kehren Sie von der Funktion zurück .
• Speichern Sie andernfalls das Präfix der Größe K , dh S[0, …, K], in einem String A und das Suffix der Größe K , dh S[N – K, …, N – 1], in einem String B .
• Kehren Sie die Zeichenfolge B um und prüfen Sie, ob A gleich B ist oder nicht. Wenn dies zutrifft, geben Sie „Ja“ aus . Geben Sie andernfalls „Nein“ aus .

Unten ist die Implementierung des obigen Ansatzes:

// 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 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 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# 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.

<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>

ja

Zeitkomplexität: O(N) 
Hilfsraum: O(N)

Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .