Bei einer Zeichenfolge str mit englischen Kleinbuchstaben können wir die folgenden zwei Operationen an der angegebenen Zeichenfolge ausführen: 

  1. Entfernen Sie die gesamte Schnur.
  2. Entfernen Sie ein Präfix der Zeichenfolge str[0…i] nur dann, wenn es gleich der Teilzeichenfolge str[(i + 1)…(2 * i + 1)] ist .

Die Aufgabe besteht darin, die maximale Anzahl von Operationen zu finden, die zum Löschen der gesamten Zeichenfolge erforderlich sind.

Beispiele:  

Eingabe: str = „abababab“ 
Ausgabe: 4 
Operation 1: Lösche das Präfix „ab“ und der String wird zu „ababab“. 
Operation 2: Löschen Sie das Präfix „ab“ und die Zeichenfolge wird zu „abab“. 
Operation 3: Präfix „ab“ löschen, str = „ab“. 
Operation 4: Löschen Sie die gesamte Zeichenfolge.

Eingabe: s = „abc“ 
Ausgabe: 1 



Ansatz: Um die Anzahl der Operationen zu maximieren, muss das zu löschende Präfix eine Mindestlänge haben, dh beginnend mit einem einzelnen Zeichen und Anhängen der aufeinanderfolgenden Zeichen nacheinander, um das Präfix mit der Mindestlänge zu finden, das die gegebene Bedingung erfüllt. Eine Operation ist erforderlich, um dieses Präfix zu löschen, z. B. str[0…i], und dann dieselbe Funktion rekursiv aufzurufen, um das Ergebnis für die Teilzeichenfolge str[i+1…2*i+1] zu finden. Wenn es kein solches Präfix gibt, das gelöscht werden könnte, geben Sie 1 zurück, da die einzige mögliche Operation darin besteht, die gesamte Zeichenfolge zu löschen.

Unten ist die Implementierung des obigen Ansatzes:  

C++

// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to return the maximum number
// of given operations required to
// remove the given string entirely
int find(string s)
{
 
    // If length of the string is zero
    if (s.length() == 0)
        return 0;
 
    // Single operation can delete the entire string
    int c = 1;
 
    // To store the prefix of the string
    // which is to be deleted
    string d = "";
 
    for (int i = 0; i < s.length(); i++) {
 
        // Prefix s[0..i]
        d += s[i];
 
        // To store the substring s[i+1...2*i+1]
        string s2 = s.substr(i + 1, d.length());
 
        // If the prefix s[0...i] can be deleted
        if (s2 == d) {
 
            // 1 operation to remove the current prefix
            // and then recursively find the count of
            // operations for the substring s[i+1...n-1]
            c = 1 + find(s.substr(i + 1));
            break;
        }
    }
 
    // Entire string has to be deleted
    return c;
}
 
// Driver code
int main()
{
    string s = "abababab";
 
    cout << find(s);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG{
   
// Function to return the maximum number
// of given operations required to
// remove the given string entirely
static int find(String s)
{
     
    // If length of the string is zero
    if (s.length() == 0)
        return 0;
   
    // Single operation can delete
    // the entire string
    int c = 1;
   
    // To store the prefix of the string
    // which is to be deleted
    String d = "";
   
    for(int i = 0; i < s.length(); i++)
    {
         
        // Prefix s[0..i]
        d += s.charAt(i);
         
        // To store the substring s[i+1...2*i+1]
        String s2 = "";
         
        if (i + d.length() < s.length())
        {
            s2 = s.substring(i + 1,
               d.length() + (i + 1));
        }
         
        // If the prefix s[0...i] can be deleted
        if (s2.equals(d))
        {
             
            // 1 operation to remove the current prefix
            // and then recursively find the count of
            // operations for the substring s[i+1...n-1]
            c = 1 + find(s.substring(i + 1));
            break;
        }
    }
   
    // Entire string has to be deleted
    return c;
}
   
// Driver code
public static void main(String[] args)
{
    String s = "abababab";
     
    System.out.print(find(s));
}
}
 
// This code is contributed by pratham76

Python3

# Python3 implementation of the approach
 
# Function to return the maximum number
# of given operations required to
# remove the given entirely
def find(s):
 
    # If length of the is zero
    if (len(s) == 0):
        return 0
 
    # Single operation can delete
    # the entire string
    c = 1
 
    # To store the prefix of the string
    # which is to be deleted
    d = ""
 
    for i in range(len(s)):
 
        # Prefix s[0..i]
        d += s[i]
 
        # To store the subs[i+1...2*i+1]
        s2 = s[i + 1:i + 1 + len(d)]
 
        # If the prefix s[0...i] can be deleted
        if (s2 == d):
 
            # 1 operation to remove the current prefix
            # and then recursively find the count of
            # operations for the subs[i+1...n-1]
            c = 1 + find(s[i + 1:])
            break
 
    # Entire has to be deleted
    return c
 
# Driver code
s = "abababab"
print(find(s))
 
# This code is contributed by Mohit Kumar

C#

// C# implementation of the approach
using System;
class GFG{
  
// Function to return the maximum number
// of given operations required to
// remove the given string entirely
static int find(string s)
{
  
    // If length of the string is zero
    if (s.Length == 0)
        return 0;
  
    // Single operation can delete the entire string
    int c = 1;
  
    // To store the prefix of the string
    // which is to be deleted
    string d = "";
  
    for (int i = 0; i < s.Length; i++)
    {
  
        // Prefix s[0..i]
        d += s[i];
  
        // To store the substring s[i+1...2*i+1]
       string s2 = "";
       if(i + d.Length < s.Length)
       {
           s2 = s.Substring(i + 1, d.Length);
       }
        
       // If the prefix s[0...i] can be deleted
       if (s2 == d)
       {
            // 1 operation to remove the current prefix
            // and then recursively find the count of
            // operations for the substring s[i+1...n-1]
            c = 1 + find(s.Substring(i + 1));
            break;
       }
    }
  
    // Entire string has to be deleted
    return c;
}
  
    // Driver code
    public static void Main(string[] args)
    {
       string s = "abababab";
       Console.Write(find(s));
    }
}
 
// This code is contributed by rutvik

Javascript

<script>
 
// Javascript implementation of the approach
 
// Function to return the maximum number
// of given operations required to
// remove the given string entirely
function find(s)
{
 
    // If length of the string is zero
    if (s.length == 0)
        return 0;
 
    // Single operation can delete the entire string
    var c = 1;
 
    // To store the prefix of the string
    // which is to be deleted
    var d = "";
 
    for (var i = 0; i < s.length; i++) {
 
        // Prefix s[0..i]
        d += s[i];
 
        // To store the substring s[i+1...2*i+1]
        var s2 = s.substring(i + 1, i+ 1+d.length);
 
        // If the prefix s[0...i] can be deleted
        if (s2 == d) {
 
            // 1 operation to remove the current prefix
            // and then recursively find the count of
            // operations for the substring s[i+1...n-1]
            c = 1 + find(s.substring(i + 1));
            break;
        }
    }
 
    // Entire string has to be deleted
    return c;
}
 
// Driver code
var s = "abababab";
document.write( find(s));
 
// This code is contributed by rrrtnx.
</script>
Ausgabe: 
4

 

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 .