Minimice el costo total de elegir K subsecuencias únicas de una string dada

Dada una string S de longitud N y un entero positivo K , la tarea es encontrar el costo total mínimo de elegir K subsecuencia única de la string S dada, de modo que el costo de elegir una subsecuencia sea la (longitud de S – longitud de esa subsecuencia) . Si es imposible elegir K subsecuencia única, imprima » -1 «.

Ejemplos:

Entrada: S = “efef”, K = 4
Salida: 3
Explicación: Hay 4 subsecuencias: “efef”, “efe”, “eef” y “fef”. 
Por lo tanto, el costo total es 0 + 1 + 1 + 1 = 3.

Entrada: S = “aaaa”, K = 40
Salida: -1

Enfoque ingenuo: el enfoque más simple es generar todas las subsecuencias distintas posibles de la string S dada y elegir K subsecuencia única de longitudes máximas posibles. Después de elegir las K subsecuencias, el resultado será ( N*K – suma de las longitudes de todas las K subsecuencias elegidas ).

Complejidad temporal: O(2 ^N )
Espacio auxiliar: O(1)

Enfoque eficiente: el enfoque anterior también se puede optimizar mediante el uso de la programación dinámica . La idea es inicializar la array DP 2D de manera que dp[i[j] signifique la suma de las longitudes de una subsecuencia única de longitud i que termina en el carácter j . Ahora, después de precomputar, elija aquellas K longitudes de subsecuencia cuya suma de longitudes sea máxima. Siga los pasos a continuación para resolver el problema:

• Inicialice la variable ans como 0.
• Inicialice una array 2D dp[N+1][128] con valor 0.
• Itere sobre el rango [0, N) usando la variable i y realice las siguientes tareas:
  • Repita los pasos [i+1, 1) usando la variable len y realice las siguientes tareas:
    • Establezca dp[len][s[i]] como acumular(dp[len – 1].begin(), dp[len – 1].end(), 0L).
  • Establezca dp[1][s[i]] como 1.
• Inicialice un vector v[N+1] con valores 0.
• Establezca v[0] como 1.
• Itere sobre el rango [1, N] usando la variable i y realice las siguientes tareas:
  • Establezca v[i] como acumular (dp[i].begin(), dp[i].end(), 0L).
• Invierta el vector v[].
• Iterar sobre un bucle for usando la variable i y realizar las siguientes tareas:
  • Inicialice una variable cantake como el mínimo de k o v[i].
  • Reste el valor cantake de k .
  • Incrementa el valor de ans por i*cantake.
• Después de realizar los pasos anteriores, imprima el valor de ans como respuesta.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum cost to
// find K unique subsequences
int minimumCost(string s, int k)
{
    int N = s.length(), ans = 0;
 
    // Stores the dp states
    vector<vector<long long> > dp(
        N + 1, vector<long long>(128, 0));
 
    // Precompute the dp states
    for (int i = 0; i < N; i++) {
 
        // Find the sum of length
        // of subsequence of length len
        // ending at index S[i]
        for (int len = i + 1; len > 1;
             len--) {
            dp[len][s[i]]
                = (accumulate(dp[len - 1].begin(),
                              dp[len - 1].end(), 0L));
        }
 
        // Sum of length of subsequence
        // of length 1
        dp[1][s[i]] = 1;
    }
    vector<long long> v(N + 1, 0);
 
    v[0] = 1;
 
    for (int i = 1; i <= N; i++) {
        v[i] += accumulate(dp[i].begin(),
                           dp[i].end(), 0L);
    }
    reverse(v.begin(), v.end());
    for (int i = 0; i < v.size() and k > 0; i++) {
        long long cantake = min<long long>(k, v[i]);
        k -= cantake;
        ans += (i * cantake);
    }
    return k > 0 ? -1 : ans;
}
 
// Driver Code
int main()
{
    string S = "efef";
    int K = 4;
    cout << minimumCost(S, K);
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG{
 
  // Function to find the minimum cost to
  // find K unique subsequences
  static int minimumCost(String s, int k)
  {
    int N = s.length(), ans = 0;
 
    // Stores the dp states
    int [][]dp = new int[N+1][128];
 
    // Precompute the dp states
    for (int i = 0; i < N; i++) {
 
      // Find the sum of length
      // of subsequence of length len
      // ending at index S[i]
      for (int len = i + 1; len > 1;
           len--) {
        dp[len][s.charAt(i)]
          = (accumulate(dp[len - 1],0,dp[len - 1].length));
      }
 
      // Sum of length of subsequence
      // of length 1
      dp[1][s.charAt(i)] = 1;
    }
    int []v = new int[N + 1];
 
    v[0] = 1;
 
    for (int i = 1; i <= N; i++) {
      v[i] += (accumulate(dp[i],0,dp[i].length));
    }
    v = reverse(v);
    for (int i = 0; i < v.length && k > 0; i++) {
      long cantake = Math.min(k, v[i]);
      k -= cantake;
      ans += (i * cantake);
    }
    return k > 0 ? -1 : ans;
  }
  static int[] reverse(int a[]) {
    int i, n = a.length, t;
    for (i = 0; i < n / 2; i++) {
      t = a[i];
      a[i] = a[n - i - 1];
      a[n - i - 1] = t;
    }
    return a;
  }
  static int accumulate(int[] arr, int start, int end){
    int sum=0;
    for(int i= 0; i < arr.length; i++)
      sum+=arr[i];
    return sum;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    String S = "efef";
    int K = 4;
    System.out.print(minimumCost(S, K));
  }
}
 
// This code contributed by shikhasingrajput

# python3 code for the above approach
 
 
def accumulate(a):
    total = 0
    for i in a:
        total += i
 
    return total
 
 
# Function to find the minimum cost to
# find K unique subsequences
def minimumCost(s, k):
    N, ans = len(s), 0
 
    # Stores the dp states
    dp = [[0 for _ in range(128)] for _ in range(N + 1)]
 
    # Precompute the dp states
    for i in range(0, N):
 
        # Find the sum of length
        # of subsequence of length len
        # ending at index S[i]
        for le in range(i + 1, 1, -1):
 
            dp[le][ord(s[i])] = (accumulate(dp[le - 1]))
 
        # Sum of length of subsequence
        # of length 1
        dp[1][ord(s[i])] = 1
 
    v = [0 for _ in range(N + 1)]
 
    v[0] = 1
 
    for i in range(1, N+1):
        v[i] += accumulate(dp[i])
 
    v.reverse()
 
    for i in range(0, len(v), 1):
        if k <= 0:
            break
        cantake = min(k, v[i])
        k -= cantake
        ans += (i * cantake)
 
    return -1 if k > 0 else ans
 
 
# Driver Code
 
if __name__ == "__main__":
 
    S = "efef"
    K = 4
    print(minimumCost(S, K))
 
    # This code is contributed by rakeshsahni

<script>
    // JavaScript code for the above approach
    function accumulate(a) {
        let total = 0;
        for (let i in a) {
            total += a[i];
        }
        return total;
    }
 
    // Function to find the minimum cost to
    // find K unique subsequences
    function minimumCost(s, k) {
        let N = s.length, ans = 0;
 
        // Stores the dp states
        let dp = new Array(N + 1)
 
        for (let i = 0; i < dp.length; i++) {
            dp[i] = new Array(128).fill(0);
        }
 
 
        // Precompute the dp states
        for (let i = 0; i < N; i++) {
 
            // Find the sum of length
            // of subsequence of length len
            // ending at index S[i]
            for (let len = i + 1; len > 1;
                len--) {
                dp[len][s[i]]
                    = (accumulate(dp[len - 1]));
            }
 
            // Sum of length of subsequence
            // of length 1
            dp[1][s[i]] = 1;
        }
        let v = new Array(N + 1).fill(0);
 
        v[0] = 1;
 
        for (let i = 1; i <= N; i++) {
            v[i] += accumulate(dp[i])
        }
        v.reverse();
        for (let i = 0; i < v.length && k > 0; i++) {
            let cantake = Math.min(k, v[i]);
            k -= cantake;
            ans += (i * cantake);
        }
        return k > 0 ? -1 : ans;
    }
 
    // Driver Code
 
    let S = "efef";
    let K = 4;
    document.write(minimumCost(S, K));
 
   // This code is contributed by Potta Lokesh
</script>

// C# program for the above approach
using System;
public class GFG
{
 
  public static int[] GetRow(int[,] matrix, int row)
  {
    var rowLength = matrix.GetLength(1);
    var rowVector = new int[rowLength];
 
    for (var i = 0; i < rowLength; i++)
      rowVector[i] = matrix[row, i];
 
    return rowVector;
  }
   
  // Function to find the minimum cost to
  // find K unique subsequences
  static int minimumCost(String s, int k) {
    int N = s.Length, ans = 0;
 
    // Stores the dp states
    int[,] dp = new int[N + 1,128];
 
    // Precompute the dp states
    for (int i = 0; i < N; i++) {
 
      // Find the sum of length
      // of subsequence of length len
      // ending at index S[i]
      for (int len = i + 1; len > 1; len--) {
        int[] row = GetRow(dp,len-1);
        dp[len,s[i]] = (accumulate(row, 0, row.Length));
      }
 
      // Sum of length of subsequence
      // of length 1
      dp[1,s[i]] = 1;
    }
    int[] v = new int[N + 1];
 
    v[0] = 1;
 
    for (int i = 1; i <= N; i++) {
      int[] row = GetRow(dp,i);
      v[i] += (accumulate(row, 0, row.Length));
    }
    v = reverse(v);
    for (int i = 0; i < v.Length && k > 0; i++) {
      long cantake = Math.Min(k, v[i]);
      k -= (int)cantake;
      ans += (int)(i * cantake);
    }
    return k > 0 ? -1 : (int)ans;
  }
 
  static int[] reverse(int []a) {
    int i, n = a.Length, t;
    for (i = 0; i < n / 2; i++) {
      t = a[i];
      a[i] = a[n - i - 1];
      a[n - i - 1] = t;
    }
    return a;
  }
 
  static int accumulate(int[] arr, int start, int end) {
    int sum = 0;
    for (int i = 0; i < arr.Length; i++)
      sum += arr[i];
    return sum;
  }
 
  // Driver Code
  public static void Main(String[] args) {
    String S = "efef";
    int K = 4;
    Console.Write(minimumCost(S, K));
  }
}
 
// This code is contributed by umadevi9616

3

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