Chương trình tìm chi phí xóa ký tự trùng lặp liên tiếp trong C++

Giới thiệu

Cho chuỗi s và mảng chi phí costs cùng độ dài. Xóa ký tự s[i] tốn costs[i]. Mục tiêu: xóa các ký tự sao cho không còn ký tự nào trùng lặp liên tiếp, với chi phí tối thiểu.

Ví dụ

s = "xxyyx", costs = [2,3,10,4,6] → Xóa s[0] (chi phí 2) và s[3] (chi phí 4) → Tổng = 6.

Ý tưởng giải thuật (Stack)

1. Duyệt chuỗi từ trái sang phải, dùng stack lưu chỉ số các ký tự đang giữ.
2. Khi gặp ký tự s[i] trùng với s[stack.top()]:
   • So sánh chi phí: giữ lại ký tự chi phí cao hơn, xóa ký tự chi phí thấp hơn.
   • Cộng chi phí của ký tự bị xóa vào kết quả.
   • Cập nhật stack: pop và push chỉ số ký tự giữ lại.
3. Nếu không trùng, push i vào stack.

Ví dụ triển khai (C++)

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

class Solution {
public:
    int minCost(string s, vector<int>& cost) {
        stack<int> 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]; // xóa ký tự hiện tại
                } else {
                    totalCost += cost[st.top()]; // xóa ký tự trên stack
                    st.pop();
                    st.push(i); // giữ ký tự hiện tại
                }
            } else {
                st.push(i);
            }
        }
        return totalCost;
    }
};

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

Đầu vào

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

Đầu ra

6