C++ এ প্রদত্ত স্ট্রিং থেকে k অনন্য অনুসৃতি খুঁজে পাওয়ার পর খরচ বের করার প্রোগ্রাম

ধরুন, আমাদের একটি স্ট্রিং s এবং আরেকটি মান k আছে। আমাদেরকে s-এর কিছু অনুসৃতি নির্বাচন করতে হবে, যাতে আমরা k-এর অনন্য অনুসৃতি পেতে পারি। এখানে, একটি অনুগামী নির্বাচনের খরচ (s)-এর দৈর্ঘ্যের সমান - (পরবর্তী) এর দৈর্ঘ্য। সুতরাং, k অনন্য অনুক্রম নির্বাচন করার পর আমাদের সর্বনিম্ন মোট খরচ খুঁজে বের করতে হবে। যদি আমরা এই সেটটি খুঁজে বের করতে না পারি, আমরা -1 ফিরে আসব। আমরা খালি স্ট্রিংটিকে একটি বৈধ পরবর্তী হিসাবে বিবেচনা করব।

সুতরাং, ইনপুট যদি s ="pqrs", k =4 এর মত হয়, তাহলে আউটপুট হবে 3।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• n :=s

  এর আকার

• আকারের একটি 2D অ্যারে ডিপি (n + 1) x (n + 1) সংজ্ঞায়িত করুন এবং এটি 0 দিয়ে আরম্ভ করুন

• শেষ একটি মানচিত্র সংজ্ঞায়িত করুন

• dp[0, 0] :=1

• আরম্ভ করার জন্য i :=0, যখন i

  • dp[i + 1, 0] :=1

  • j আরম্ভ করার জন্য :=(i + 1), যখন j>=1, আপডেট করুন (j 1 দ্বারা কম করুন), −

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

  • যদি s[i] শেষের শেষ উপাদান না হয়, তাহলে -

    • j শুরু করার জন্য :=0, যখন j <=শেষ[s[i]], আপডেট করুন (j 1 দ্বারা বাড়ান), −

      • dp[i + 1, j + 1] - =dp[শেষ[s[i]], j]

  • শেষ [s[i]] :=i

• খরচ :=0

• আরম্ভ করার জন্য i :=n, যখন i>=0, আপডেট করুন (i 1 দ্বারা কম করুন), −

  • val :=ন্যূনতম k এবং dp[n, i]

  • খরচ :=খরচ + (val * (n - i))

  • k :=k - dp[n, i]

  • যদি k <=0, তাহলে −

    • লুপ থেকে বেরিয়ে আসুন

• যদি k <=0, তাহলে −

  • ফেরত খরচ

• রিটার্ন -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

আউটপুট

3