Hiểu bài toán

Cho hai input là số nguyên k và một chuỗi ký tự số (số tự nhiên). Nhiệm vụ là loại bỏ đúng k ký tự khỏi chuỗi để thu được một số tự nhiên lớn nhất có thể. Các ký tự được loại bỏ không nhất thiết phải liên tiếp. Ví dụ: với k=2 và chuỗi "1432", ta có thể xóa '1' và '4' để được "32", hoặc xóa '3' và '2' để được "14", v.v. Số lớn nhất thu được là "432".

Các cách tiếp cận

Cách Greedy với Stack (Sử dụng vector/stack)

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

int main() {
    freopen("MAXNUM.INP", "r", stdin);
    freopen("MAXNUM.OUT", "w", stdout);

    int k;
    string s;
    cin >> k >> s;

    int n = s.size();
    string res;

    for (char c : s) {
        // Lặp khi stack không rỗng, còn số lượng có thể xóa, và ký tự ở đỉnh nhỏ hơn ký tự hiện tại
        while (!res.empty() && k > 0 && res.back() < c) {
            res.pop_back();
            k--;
        }
        res.push_back(c);
    }

    // Nếu sau khi duyệt hết chuỗi vẫn chưa xóa đủ k ký tự, xóa từ cuối chuỗi kết quả
    while (k > 0 && !res.empty()) {
        res.pop_back();
        k--;
    }

    cout << res << '\n';
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Sử dụng một stack (hoặc string đóng vai trò như stack) để xây dựng kết quả. Duyệt từng ký tự trong chuỗi đầu vào:

1. Nếu ký tự hiện tại lớn hơn ký tự ở đỉnh stack và ta vẫn còn quota để xóa (k > 0), ta pop ký tự ở đỉnh stack ra. Cứ lặp lại cho đến khi điều kiện này không thỏa mãn.
2. Push ký tự hiện tại vào stack. Sau khi duyệt hết, nếu stack có độ dài lớn hơn n - k, ta cần xóa bớt các ký tự ở cuối (vì đây là trường hợp chuỗi kết quả tăng dần, xóa các số ở cuối sẽ cho số lớn nhất). Cách này đảm bảo ta ưu tiên giữ lại các chữ số có giá trị lớn ở vị trí cao nhất có thể.

Cách Thư viện chuẩn (Standard Library)

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

int main() {
    freopen("MAXNUM.INP", "r", stdin);
    freopen("MAXNUM.OUT", "w", stdout);

    int k;
    string s;
    cin >> k >> s;

    string res = "";
    for (char c : s) {
        while (res.size() && k && res.back() < c) {
            res.pop_back();
            k--;
        }
        res.push_back(c);
    }

    while (k--) res.pop_back();

    cout << res;
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Đây là biến thể tối ưu hóa cú pháp của Approach 1. Logic hoàn toàn giống nhau: duy trì một chuỗi res tăng dần尽可能 lớn. Nếu gặp một ký tự mới lớn hơn, ta loại bỏ các ký tự nhỏ hơn ở cuối chuỗi res để chèn ký tự mới vào. Đây là giải thuật chuẩn để giải quyết bài toán này.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Thứ tự các chữ số có ảnh hưởng lớn hơn giá trị của chúng. Việc tối ưu hóa vị trí (ví dụ biến '2' thành '5' ở hàng nghìn) quan trọng hơn việc tối ưu hóa giá trị tại cùng một vị trí (ví dụ '5' thành '8'). Do đó, ta nên ưu tiên loại bỏ các chữ số nhỏ ở đầu nếu có một chữ số lớn hơn xuất hiện ở sau.
• Giải thuật Greedy kết hợp Stack là chính xác: 'Nếu gặp số lớn hơn, hãy vứt bỏ số nhỏ hơn trước đó'.

Lỗi thường gặp

• Quên xử lý trường hợp sau khi duyệt hết chuỗi input mà vẫn còn k > 0. Ví dụ input là "12345" và k=2. Thuật toán sẽ duyệt hết và giữ nguyên chuỗi "12345". Lúc này ta phải xóa 2 ký tự cuối cùng để được "123".
• Xử lý sai trường hợp chuỗi input có các ký tự giống nhau. Ví dụ "999", k=1. Ta không nên xóa bất kỳ ký tự nào vì xóa ký tự nào cũng giảm độ dài mà không tăng giá trị (các số đầu đều là 9). Tuy nhiên, thuật toán chuẩn vẫn sẽ xóa ký tự cuối nếu k>0 sau vòng lặp.