從給定字串 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 函式，它將執行自定義排序。