কনsekutিভ ডুপ্লিকেট ক্যারেক্টার মুছে ফেলার ন্যূনতম খরচ C++-এ

একটি স্ট্রিং এবং প্রতিটি ক্যারেক্টারের মুছে ফেলার খরচ (costs) দেওয়া আছে। কনsekutিভ ডুপ্লিকেট ক্যারেক্টারগুলো মুছে ফেলতে হবে এমনভাবে যে মোট খরচ ন্যূনতম হয়। প্রতিটি গোষ্ঠীতে সবচেয়ে কম খরচের ক্যারেক্টারগুলো মুছে ফেললেই ন্যূনতম খরচ পাওয়া যায়।

উদাহরণ

স্ট্রিং: "xxyyx"

খরচ: [2, 3, 10, 4, 6]

আউটপুট: 6

ব্যাখ্যা: প্রথম 'x' (খরচ ২) এবং চতুর্থ 'y' (খরচ ৪) মুছে ফেলা → মোট ৬।

অ্যালগরিদম (স্ট্যাক ব্যবহার)

একটি স্ট্যাক রেখে ইন্ডেক্স ট্র্যাক করুন।
প্রতিটি ক্যারেক্টারের জন্য:
- যদি স্ট্যাকের টপের ক্যারেক্টার বর্তমান ক্যারেক্টারের সমান হয়:
  - দুটোর খরচ তুলনা করুন।
  - বেশি খরচেরটি রাখুন, কম খরচেরটি মোট খরচে যোগ করুন।
  - স্ট্যাক আপডেট করুন।
- অন্যথায় বর্তমান ইন্ডেক্স স্ট্যাকে পুশ করুন।

C++ কোড উদাহরণ

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

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

int main() {
    Solution ob;
    string s = "xxyyx";
    vector v = {2, 3, 10, 4, 6};
    cout << ob.minCost(s, v);
    return 0;
}

ইনপুট

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