Número máximo de operaciones dadas para eliminar toda la string

Dada la string str que contiene caracteres ingleses en minúsculas, podemos realizar las siguientes dos operaciones en la string dada: 

1. Retire toda la string.
2. Elimina un prefijo de la string str[0…i] solo si es igual a la substring str[(i + 1)…(2 * i + 1)] .

La tarea es encontrar el número máximo de operaciones necesarias para eliminar toda la string.

Ejemplos:  

Entrada: str = “abababab” 
Salida: 4 
Operación 1: Eliminar el prefijo “ab” y la string se convierte en “ababab”. 
Operación 2: elimine el prefijo «ab» y la string se convierte en «abab». 
Operación 3: Eliminar el prefijo “ab”, str = “ab”. 
Operación 4: Eliminar toda la string.

Entrada: s = “abc” 
Salida: 1 

Enfoque: para maximizar el número de operaciones, el prefijo que se eliminará debe tener una longitud mínima, es decir, comenzar desde un solo carácter y agregar los caracteres sucesivos uno por uno para encontrar el prefijo de longitud mínima que satisfaga la condición dada. Se requerirá una operación para eliminar este prefijo, digamos str[0…i], luego llame recursivamente a la misma función para encontrar el resultado de la substring str[i+1…2*i+1]. Si no existe tal prefijo que pueda eliminarse, devuelva 1 ya que la única operación posible es eliminar la string completa.

A continuación se muestra la implementación del enfoque anterior:  

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

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

4

Tiempo Complejidad: O(N ² )
Espacio Auxiliar: O(N)