Movimientos mínimos para formar una string agregando caracteres o agregando la propia string

Dada una string S, necesitamos escribir un programa para verificar si es posible construir la string S dada realizando cualquiera de las siguientes operaciones cualquier cantidad de veces. En cada paso, podemos:

• Agregue cualquier carácter al final de la string.
• o agregue la string a la propia string.

Los pasos anteriores se pueden aplicar cualquier número de veces. Necesitamos escribir un programa para imprimir los pasos mínimos requeridos para formar la string.

Ejemplos:

Input : aaaaaaaa
Output : 4 
Explanation: move 1: add 'a' to form "a"
move 2: add 'a' to form "aa"
move 3: append "aa" to form "aaaa" 
move 4: append "aaaa" to form "aaaaaaaa" 

Input: aaaaaa
Output: 4 
Explanation: move 1: add 'a' to form "a"
move 2: add 'a' to form "aa"
move 3: add 'a' to form "aaa" 
move 4: append "aaa" to form "aaaaaa" 

Input: abcabca
Output: 5  

La idea para resolver este problema es usar Programación Dinámica para contar el número mínimo de movimientos. Cree una array denominada dp de tamaño n, donde n es la longitud de la string de entrada. dp[i] almacena el número mínimo de movimientos que se requieren para hacer una substring (0…i). De acuerdo con la pregunta, hay dos movimientos que son posibles:

1. dp[i] = min(dp[i], dp[i-1] + 1) que significa adición de caracteres.
2. dp[i*2+1] = min(dp[i]+1, dp[i*2+1]) , la adición de la string se realiza si s[0…i]==s[i+1..i *2+1]

La respuesta se almacenará en dp[n-1] ya que necesitamos formar la string (0..n-1) en el índice.

A continuación se muestra la implementación de la idea anterior:

C++

// CPP program to print the // Minimal moves to form a string // by appending string and adding characters #include <bits/stdc++.h> using namespace std;    // function to return the minimal number of moves int minimalSteps(string s, int n) {        int dp[n];        // initializing dp[i] to INT_MAX     for (int i = 0; i < n; i++)         dp[i] = INT_MAX;        // initialize both strings to null     string s1 = "", s2 = "";            // base case     dp[0] = 1;        s1 += s[0];        for (int i = 1; i < n; i++) {         s1 += s[i];            // check if it can be appended         s2 = s.substr(i + 1, i + 1);            // addition of character takes one step         dp[i] = min(dp[i], dp[i - 1] + 1);            // appending takes 1 step, and we directly         // reach index i*2+1 after appending         // so the number of steps is stord in i*2+1         if (s1 == s2)             dp[i * 2 + 1] = min(dp[i] + 1, dp[i * 2 + 1]);     }        return dp[n - 1]; }    // Driver Code int main() {        string s = "aaaaaaaa";     int n = s.length();        // function call to return minimal number of moves     cout << minimalSteps(s, n);        return 0; }

Java

// Java program to print the // Minimal moves to form a string // by appending string and adding characters import java.util.*;    class GFG {    // function to return the minimal number of moves static int minimalSteps(String s, int n) {        int []dp = new int[n];            // initializing dp[i] to INT_MAX     for (int i = 0; i < n; i++)         dp[i] = Integer.MAX_VALUE;        // initialize both strings to null     String s1 = "", s2 = "";            // base case     dp[0] = 1;        s1 += s.charAt(0);        for (int i = 1; i < n; i++)     {         s1 += s.charAt(i);            // check if it can be appended         s2 = s.substring(i + 1, i + 1);            // addition of character takes one step         dp[i] = Math.min(dp[i], dp[i - 1] + 1);            // appending takes 1 step, and we directly         // reach index i*2+1 after appending         // so the number of steps is stord in i*2+1         if (s1 == s2)             dp[i * 2 + 1] = Math.min(dp[i] + 1,                                     dp[i * 2 + 1]);     }     return dp[n - 1]; }    // Driver Code public static void main(String args[]) {        String s = "aaaaaaaa";     int n = s.length();        // function call to return minimal number of moves     System.out.println(minimalSteps(s, n)/2); } }    // This code is contributed by  // Shashank_Sharma

Python3

# Python program to print the  # Minimal moves to form a string  # by appending string and adding characters     INT_MAX = 100000000    # function to return the  # minimal number of moves  def minimalSteps(s, n):     dp = [INT_MAX for i in range(n)]             # initialize both strings to null      s1 = ""     s2 = ""            # base case      dp[0] = 1     s1 += s[0]            for i in range(1, n):         s1 += s[i]                # check if it can be appended          s2 = s[i + 1: i + 1 + i + 1]                # addition of character          # takes one step          dp[i] = min(dp[i], dp[i - 1] + 1)                # appending takes 1 step, and          # we directly reach index i*2+1          # after appending so the number         # of steps is stord in i*2+1          if (s1 == s2):              dp[i * 2 + 1] = min(dp[i] + 1,                                  dp[i * 2 + 1])            return dp[n - 1]    # Driver Code  s = "aaaaaaaa" n =len(s)    # function call to return  # minimal number of moves  print( minimalSteps(s, n) )     # This code is contributed  # by sahilshelangia

C#

// C# program to print the // Minimal moves to form a string // by appending string and adding characters using System;        class GFG {    // function to return the minimal number of moves static int minimalSteps(String s, int n) {        int []dp = new int[n];            // initializing dp[i] to INT_MAX     for (int i = 0; i < n; i++)         dp[i] = int.MaxValue;        // initialize both strings to null     String s1 = "", s2 = "";            // base case     dp[0] = 1;        s1 += s[0];        for (int i = 1; i < n; i++)     {         s1 += s[i];            // check if it can be appended         s2 = s.Substring(i , 1);            // addition of character takes one step         dp[i] = Math.Min(dp[i], dp[i - 1] + 1);            // appending takes 1 step, and we directly         // reach index i*2+1 after appending         // so the number of steps is stord in i*2+1         if (s1 == s2)             dp[i * 2 + 1] = Math.Min(dp[i] + 1,                                  dp[i * 2 + 1]);     }     return dp[n - 1]; }    // Driver Code public static void Main(String []args) {        String s = "aaaaaaaa";     int n = s.Length;        // function call to return minimal number of moves     Console.Write(minimalSteps(s, n)/2); } }    // This code has been contributed by 29AjayKumar

PHP

<?php // php program to print the // Minimal moves to form a  // string by appending string // and adding characters    // function to return the // minimal number of moves function minimalSteps($s,$n) {        // initializing dp[i] to INT_MAX     for ($i = 0; $i < $n; $i++)         $dp[$i] = PHP_INT_MAX;        // initialize both      // strings to null     $s1 = "";     $s2 = "";            // base case     $dp[0] = 1;        $s1=$s1.$s[0];        for ($i = 1; $i < $n; $i++)      {         $s1 = $s1.$s[$i];            // check if it can          // be appended         $s2 = substr($s, $i + 1, $i + 1);            // addition of character         // takes one step         $dp[$i] = min($dp[$i],                    $dp[$i - 1] + 1);            // appending takes 1 step,         // and we directly         // reach index i*2+1          // after appending         // so the number of steps          // is stord in i*2+1         if ($s1 == $s2)             $dp[$i * 2 + 1] = min($dp[$i] + 1,                               $dp[$i * 2 + 1]);     }        return $dp[$n - 1]; }        // Driver Code     $s = "aaaaaaaa";     $n = strlen($s);        // function call to return     //minimal number of moves     echo minimalSteps($s, $n);    // This code is contributed by mits  ?>

Producción:

4

Complejidad de tiempo: O (n ² ), donde n es la longitud de la string de entrada.