在C ++中从给定字符串中找到k个唯一子序列后查找成本的程序

假设我们有一个字符串s和另一个值k。我们必须选择s的一些子序列，以便获得k个唯一的子序列。在此，选择子序列的成本等于(s)的长度-（子序列的）长度。因此，我们必须在选择k个唯一子序列后找到最低的总成本。如果我们无法找到该集合，则将返回-1。我们将空字符串视为有效的子序列。

因此，如果输入类似于s =“ pqrs”，k = 4，则输出将为3。

在线示例

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h>
using namespace std;
int solve(string s, int k) {
   int n = s.size();
   vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
   unordered_map<char, int> last;
   dp[0][0] = 1;
   for (int i = 0; i < n; i++) {
      dp[i + 1][0] = 1;
      for (int j = (i + 1); j >= 1; j--) {
         dp[i + 1][j] = dp[i][j] + dp[i][j - 1];
      }
      if (last.find(s[i]) != last.end()) {
         for (int j = 0; j <= last[s[i]]; j++) {
            dp[i + 1][j + 1] -= dp[last[s[i]]][j];
         }
      }
      last[s[i]] = i;
   }
   int cost = 0;
   for (int i = n; i >= 0; i--) {
      int val = min(k, dp[n][i]);
      cost += (val * (n - i));
      k -= dp[n][i];
      if (k <= 0) {
         break;
      }
   }
   if (k <= 0) {
      return cost;
   }
   return -1;
}
int main(){
   cout << solve("pqrs",4) << endl;
   return 0;
}

输入：

"pqrs", 4

3