Hiểu bài toán

Bài toán yêu cầu nén chuỗi ký tự bằng cách thay thế các dãy ký tự lặp lại liên tiếp nhau bằng số lần lặp và ký tự đó. Ví dụ: chuỗi 'aabbcc' sẽ được nén thành '2a2b2c'. Đầu vào là một chuỗi ký tự in thường, đầu ra là chuỗi đã được nén theo định dạng trên.

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

Cách Duyệt tuần tự với biến đếm

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

int main() {
    string s;
    cin >> s;

    int cnt = 1;
    for (int i = 1; i <= s.length(); i++) {
        if (i < s.length() && s[i] == s[i - 1]) {
            cnt++;
        } else {
            cout << cnt << s[i - 1];
            cnt = 1;
        }
    }
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Cách tiếp cận này sử dụng một vòng lặp để duyệt qua chuỗi. Biến cnt đếm số lượng ký tự giống nhau liên tiếp. Khi gặp một ký tự khác hoặc kết thúc chuỗi, ta in ra số đếm và ký tự đó, sau đó đặt lại cnt về 1. Vòng lặp chạy từ index 1 đến độ dài chuỗi, so sánh ký tự hiện tại với ký tự trước đó.

Cách Duyệt theo nhóm (Grouping)

#include <bits/stdc++.h> 
using namespace std;
int main(){
ios_base::sync_with_stdio(false);cin.tie(nullptr);string s;cin>>s;int i=0;while(i<s.size()){int cnt = 1;while(i+cnt<s.size() && s[i+cnt] == s[i]) cnt++;cout<<cnt<<s[i];i+=cnt;}}

• Time Complexity: O(n)
• Space Complexity: O(1)

Cách tiếp cận này sử dụng một vòng lặp while bên ngoài để duyệt qua các nhóm ký tự. Trong mỗi nhóm, một vòng lặp while bên trong đếm số lượng ký tự giống nhau liên tiếp (tính cả ký tự đầu tiên). Sau khi đếm xong một nhóm, in kết quả và nhảy chỉ số i đến vị trí bắt đầu của nhóm tiếp theo.

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

Bài học kinh nghiệm

• Bài toán có thể giải quyết bằng cách đếm số lượng ký tự lặp lại liên tiếp và in ra khi nhóm đó kết thúc.
• Cần xử lý ký tự cuối cùng của chuỗi một cách cẩn thận để đảm bảo nó được in ra đầy đủ.

Lỗi thường gặp

• Quên kiểm tra điều kiện index < độ dài chuỗi khi truy cập phần tử mảng/string (truy cập ngoài biên).
• Lỗi logic khi in kết quả, ví dụ in sai thứ tự hoặc in thừa ký tự.