Lời giải: Xóa ký tự trùng liên tiếp

Phân tích

Duyệt xâu, với mỗi ký tự, kiểm tra xem nó có khác với ký tự cuối cùng của xâu kết quả hay không. Nếu khác (hoặc xâu kết quả rỗng), thêm ký tự đó vào.

Độ phức tạp

• Thời gian: O(N)
• Không gian: O(N)

Code mẫu C++

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

int main() {
    string s;
    cin >> s;
    string res = "";
    for (char c : s) {
        // Chỉ thêm ký tự nếu xâu kết quả rỗng hoặc khác với ký tự cuối
        if (res.empty() || res.back() != c) {
            res += c;  // Thêm ký tự vào xâu kết quả
        }
        // Nếu cùng ký tự với ký tự cuối, bỏ qua (đã được "gộp")
    }
    cout << res << endl;
    return 0;
}

Giải thích

• Cách làm này tương đương với một máy trạng thái đơn giản: luôn giữ lại ký tự cuối cùng khác biệt.
• res.back() lấy ký tự cuối cùng của xâu kết quả mà không cần truy cập chỉ số.
• Chỉ "xóa" các ký tự trùng liên tiếp, không phải trùng ở vị trí bất kỳ.