सी ++ में लागत के साथ लगातार डुप्लिकेट वर्णों को हटाने के लिए लागत खोजने का कार्यक्रम?

मान लीजिए कि हमारे पास लोअरकेस अक्षरों वाला एक स्ट्रिंग है और हमारे पास गैर-ऋणात्मक मानों की एक सूची भी है, जिन्हें लागत कहा जाता है, स्ट्रिंग और सूची की लंबाई समान होती है। हम लागत लागत [i] के लिए वर्ण s [i] हटा सकते हैं, और फिर s [i] और लागत [i] दोनों हटा दिए जाते हैं। हमें लगातार दोहराए जाने वाले सभी वर्णों को हटाने के लिए न्यूनतम लागत का पता लगाना होगा।

इसलिए, यदि इनपुट s ="xxyyx" nums =[2, 3, 10, 4, 6] जैसा है, तो आउटपुट 6 होगा, क्योंकि हम कुल लागत के लिए s [0] और s [3] को हटाते हैं। 2 + 4 =6.

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे

एक स्टैक सेंट परिभाषित करें
लागत :=0
इनिशियलाइज़ करने के लिए:=0, जब मैं <साइज़ ऑफ़ s, अपडेट (i 1 से बढ़ाएँ), यह करें:
- यदि st का आकार 0 नहीं है और s[st का शीर्ष] s[i] के समान है, तो:
  - यदि अंक [सेंट के शीर्ष]> अंक [i], तो:
    - लागत:=लागत + अंक[i]
  - अन्यथा:
    - लागत :=लागत + अंक [सेंट के ऊपर]
    - सेंट से पॉप तत्व
    - मुझे सेंट में धकेलें
- अन्यथा
  - मुझे सेंट में धकेलें
वापसी लागत

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें

उदाहरण

#include <bits/stdc++.h>
using namespace std;

class Solution {
   public:
   int solve(string s, vector<int>& nums) {
      stack<int> st;
      int cost = 0;
      for (int i = 0; i < s.size(); ++i) {
         if (st.size() && s[st.top()] == s[i]) {
            if (nums[st.top()] > nums[i]) {
               cost += nums[i];
            } else {
               cost += nums[st.top()];
               st.pop();
               st.push(i);
            }
         } else {
            st.push(i);
         }
      }
      return cost;
   }
};


int solve(string s, vector<int>& nums) {
   return (new Solution())->solve(s, nums);
}

main(){
   vector<int> v = {2, 3, 10, 4, 6};
   string s = "xxyyx";
   cout << solve(s, v);
}

इनपुट

"xxyyx",{2,3,10,4,6}