从给定字符串 S 中构造长度为 K 的子序列的最小成本

---

我们将得到一个长度为 n 的字符串、一个整数 k 和一个长度为 26 的整数数组。整数数组定义了每个小写字符的成本，并且字符串将仅包含小写字母。我们必须从给定字符串中创建一个长度为 k 的子序列，以获得尽可能低的成本。我们将使用排序来解决问题，并将实现一个带有完整解释的代码。

示例

输入 1

给定字符串：acbcbac

给定数字：4

给定数组：{2,3,1,2,4,5,5,6,6,2,1,0,4,3,5,2,3,6,2,6,0,9,3,1,5,6}

输出 1：6 (acca)

解释 - 上述代码的输出基于元素或字符的成本。我们有三个不同的字符 a、b 和 c。c 的成本最低，而与 b 相比，a 的成本更优。

输入 2

给定字符串：zxay

给定数字：2

给定数组：{2,3,1,2,4,5,5,6,6,2,1,0,4,3,5,2,3,6,2,6,0,9,3,1,5,6}

输出 2：3 (xa)

解释 - 同样的原因或解释，这里 x 和 a 的成本与两者相比最低。

排序方法

在这种方法中，我们将创建一个额外的字符串，它将是给定字符串的副本。

我们将使用 sort 函数和内联 lambda 函数对临时字符串进行排序。

Lambda 函数是可以在 STL 函数中插入的内联函数，用于更改排序优先级的方式。

排序后，我们将只遍历字符串的前 k 个字符，并将它们的成本添加到 answer 变量中，并返回该变量。

示例

#include <bits/stdc++.h>
using namespace std;
// function to find the required string 
int getString(string str, int k, int cost[]){
   // creating a temporary string 
   string temp = str;    
   // sorting the temporary string on the basis of the priority of the elements 
   sort(temp.begin(),temp.end(),[&](char a, char b){
      return cost[a-'a'] < cost[b-'a']; 
   });    
   int ans = 0; // variable to store the answer     
   // getting cost of the first k elements     
   for(int i=0; i<k; i++){
      ans += cost[temp[i]-'a'];
   }
   return ans;
}
int main(){
   string str = "acbacaz"; // given string 
   int k = 5; // size of subsequence    
   // cost array
   int cost[] = {2,3,1,2,4,5,5,6,6,2,1,0,4,3,5,2,3,6,2,6,0,9,3,1,5,6};
   // calling the function to get the string 
   int req = getString(str,k,cost);
   cout<<"Cost for the subsequence with the lowest cost of size "<< k << " is "<<req<<endl;
   return 0;
}

输出

Cost for the subsequence with the lowest cost of size 5 is 8

时间和空间复杂度

上述代码的时间复杂度为 O(N*log(N))，其中 N 是数组的大小。我们正在对数组进行排序，从而带来对数因子。

上述代码的空间复杂度为 O(N)，这是由于创建了临时字符串。

多重集方法

在这种方法中，我们将遍历字符串并将元素添加到集合中。

如果集合的大小小于 k，则我们可以直接将该元素添加到集合中，并将成本添加到 answer 变量中。

如果集合的大小等于 k，则我们将比较当前字符的成本与多重集中存在的最大成本。

如果成本较低，我们将删除最后一个元素并减少该成本，并将新成本添加到多重集以及 answer 中。

最后，我们将返回成本。我们也可以使用优先队列数据结构而不是多重集。

示例

#include <bits/stdc++.h>
using namespace std;
// function to find the required string 
int getString(string str, int k, int cost[]){    
   // iterating over the string and adding the cost to set 
   multiset<int>st;
   int ans = 0;
   for(int i =0; i< str.length() ;i++){
      if(st.size() < k){
         ans += cost[str[i]-'a'];
         st.insert(cost[str[i]-'a']);
      }
      else{
         if(*st.rbegin() > cost[str[i]-'a']){
            ans -= *st.rbegin()-cost[str[i]-'a'];
            st.insert(cost[str[i]-'a']);
            st.erase(*st.rbegin());
         }
      }
   }
   return ans;
}
int main(){
   string str = "acbacaz"; // given string 
   int k = 5; // size of subsequence    
   // cost array
   int cost[] = {2,3,1,2,4,5,5,6,6,2,1,0,4,3,5,2,3,6,2,6,0,9,3,1,5,6};
   // calling the function to get the string 
   int req = getString(str,k,cost);    
   cout<<"The cost for the subsequence with the lowest cost of size "<< k << " is "<<req<<endl;
   return 0;
}

输出

The cost for the subsequence with the lowest cost of size 5 is 8

时间和空间复杂度

上述代码的时间复杂度为 O(N*log(K))，其中 N 是字符串的大小，k 是所需子序列的大小。

上述代码的空间复杂度为 O(K)，因为集合的最大大小将为 K。

注意：我们也可以在这里使用优先队列数据结构来查找最小成本，并且该方法将带来更简洁的代码。因为，使用优先队列更容易访问最大成本。

结论

在本教程中，我们实现了一个程序来查找从给定字符串创建子序列所需的最小成本，其中每个字符的成本都是给定的。我们实现了一种多重集方法和另一种排序方法。对于排序方法，我们使用了 lambda 函数，它将执行自定义排序。