C++-এ স্ট্রিং থেকে K ইউনিক সাবসিকোয়েন্স বের করার খরচ নির্ণয় করুন

মান লিজিয়ে একটি স্ট্রিং s এবং একটি মান k আছে। আমাদের s-এর কিছু সাবসিকোয়েন্স সিলেক্ট করতে হবে যাতে kটি ইউনিক সাবসিকোয়েন্স পাওয়া যায়। একটি সাবসিকোয়েন্স সিলেক্ট করার খরচ = s-এর দৈর্ঘ্য - সাবসিকোয়েন্সের দৈর্ঘ্য। আমাদের kটি ইউনিক সাবসিকোয়েন্স সিলেক্ট করার ন্যূনতম মোট খরচ বের করতে হবে। যদি সম্ভব না হয়, -1 রিটার্ন করুন। খালি স্ট্রিংকে বৈধ সাবসিকোয়েন্স মনে করা হয়।

যেমন s = "pqrs", k = 4 হলে আউটপুট হবে ৩।

সমাধানের ধাপগুলো:

n := s.size()
(n+1)x(n+1) আকারের 2D অ্যারে dp ০ দিয়ে ইনিশিয়ালাইজ করুন
last নামক একটি ম্যাপ সংজ্ঞায়িত করুন
dp[0][0] := 1
i=0 থেকে n-1 পর্যন্ত:

dp[i+1][0] := 1
j=i+1 থেকে ১ পর্যন্ত কমাতে কমাতে:

dp[i+1][j] := dp[i][j] + dp[i][j-1]

যদি s[i] last-এ না থাকে:

j=0 থেকে last[s[i]] পর্যন্ত dp[i+1][j+1] -= dp[last[s[i]]][j]

last[s[i]] := i

cost := 0
i=n থেকে ০ পর্যন্ত কমাতে কমাতে:

val := min(k, dp[n][i])
cost += val * (n - i)
k -= dp[n][i]
যদি k <= 0, ব্রেক করুন

যদি k <= 0, cost রিটার্ন করুন, অন্যথায় -1

উদাহরণ

নিচের ইমপ্লিমেন্টেশন দেখুন:

#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