परिचय
मान लीजिए, हमारे पास एक स्ट्रिंग s और एक अन्य मान k है। हमें s के कुछ सबसीक्वेंसेस (subsequences) चुनने हैं, ताकि हमें k अद्वितीय सबसीक्वेंसेस मिल सकें। यहां, एक सबसीक्वेंस चुनने की लागत length(s) - length(subsequence) के बराबर होती है। तो, हमें k अद्वितीय सबसीक्वेंसेस चुनने के बाद न्यूनतम कुल लागत ढूंढनी है। यदि हम इस सेट को ढूंढने में असमर्थ हैं, तो हम -1 वापस करेंगे। हम खाली स्ट्रिंग को एक वैध सबसीक्वेंस मानेंगे।
तो, यदि इनपुट s = "pqrs", k = 4 है, तो आउटपुट 3 होगा।
समाधान दृष्टिकोण
डायनामिक प्रोग्रामिंग का उपयोग करके dp[i][j] = s के पहले i कैरेक्टर्स का उपयोग करके लंबाई j के अद्वितीय सबसीक्वेंसेस की संख्या। फिर लालची तरीके से सबसे लंबे सबसीक्वेंसेस पहले चुनें (कम लागत)।
उदाहरण कोड
#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
व्याख्या
"pqrs" के अद्वितीय सबसीक्वेंसेस: लंबाई 4: "pqrs" (1), लंबाई 3: "pqr", "pqs", "prs", "qrs" (4), लंबाई 2: 6, लंबाई 1: 4, लंबाई 0: 1।
k=4 के लिए: सबसे लंबे चुनें: "pqrs" (लागत 0), फिर लंबाई 3 से 3 सबसीक्वेंसेस (लागत 1 प्रत्येक) = कुल लागत 3।
निष्कर्ष
DP टेबल सभी लंबाई के अद्वितीय सबसीक्वेंसेस गिनता है, डुप्लिकेट कैरेक्टर्स को हैंडल करते हुए। लालची चयन न्यूनतम लागत सुनिश्चित करता है। यदि आपके कोई प्रश्न हैं, तो कमेंट सेक्शन में पूछें।