Hiểu bài toán

Bài toán yêu cầu xử lý n xâu ký tự. Với mỗi xâu, ta cần tìm ký tự đầu tiên xuất hiện duy nhất một lần (tần suất bằng 1) trong xâu đó và in ra nó. Nếu không có ký tự nào thỏa mãn, có thể in ra một ký tự đặc biệt hoặc kết thúc xâu (tùy theo yêu cầu đề bài ngầm định, nhưng các solution đều chỉ in ra khi tìm thấy).

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

Cách Sử dụng Map (Hash Map)

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("matkhau.inp","r",stdin);
    freopen("matkhau.out","w",stdout);
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        map<char,int>a;
        for(auto i:s)a[i]++;
        for(auto i:a){
            if(i.second==1){
                cout<<i.first;
                break;
            }
        }
    }
}

• Time Complexity: O(N * L log K)
• Space Complexity: O(K)

Phương pháp này sử dụng một map (hoặc hash map) để đếm tần suất của từng ký tự trong xâu.

1. Duyệt qua từng ký tự của xâu, tăng giá trị đếm tương ứng trong map.
2. Sau đó, duyệt qua các phần tử của map. Do map mặc định được sắp xếp theo khóa (key), việc duyệt từ đầu sẽ đảm bảo ta gặp ký tự có thứ tự từ điển nhỏ nhất trước.
3. Khi gặp ký tự đầu tiên có tần suất bằng 1, in ra và dừng lại cho xâu hiện tại. Độ phức tạp: Với mỗi xâu độ dài L, xây dựng map mất O(L log K) (K là số ký tự khác nhau, tối đa 256 hoặc 52). Duyệt map mất O(K log K). Tổng thể O(N * L log L).

Cách Mảng đếm tần suất (Frequency Array)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("matkhau.inp","r",stdin);
    freopen("matkhau.out","w",stdout);

    int n;
    cin >> n;
    while(n--) {
        string s;
        cin >> s;
        // Giả sử input chỉ gồm chữ cái in hoa/thường và số, mảng 256 là đủ
        // Khởi tạo mảng đếm cho mỗi xâu
        int cnt[256] = {0};

        // Đếm tần suất
        for (char c : s) {
            cnt[(unsigned char)c]++;
        }

        // Tìm ký tự đầu tiên có tần suất 1
        bool found = false;
        for (char c : s) {
            if (cnt[(unsigned char)c] == 1) {
                cout << c;
                found = true;
                break;
            }
        }
        // Nếu không tìm thấy, có thể không in gì hoặc in theo yêu cầu đề bài
    }
    return 0;
}

• Time Complexity: O(N * L)
• Space Complexity: O(1) (fixed size array)

Thay vì dùng map, ta dùng mảng固定大小 (ví dụ 256 phần tử cho các ký tự ASCII) để đếm tần suất.

1. Khởi tạo mảng đếm bằng 0 cho mỗi xâu.
2. Duyệt xâu để đếm tần suất vào mảng.
3. Duyệt lại xâu từ đầu (để đảm bảo lấy ký tự xuất hiện đầu tiên), kiểm tra xem tần suất trong mảng có bằng 1 không. Nếu có, in ra và dừng. Phương pháp này tối ưu hơn Map về tốc độ do truy cập mảng trực tiếp O(1) thay vì O(log K).

Cách Optimized: Counting Sort & First Occurrence

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("matkhau.inp","r",stdin);
    freopen("matkhau.out","w",stdout);

    int n;
    cin >> n;
    // Mảng đếm toàn cục hoặc tái sử dụng, nhưng cần reset.
    // Để đơn giản, dùng map hoặc mảng 256 trong vòng lặp là an toàn nhất.
    // Code dưới đây là ví dụ dùng mảng 256.

    while(n--) {
        string s;
        cin >> s;
        int cnt[256] = {0};

        // Bước 1: Đếm tần suất
        for (char c : s) {
            cnt[(unsigned char)c]++;
        }

        // Bước 2: Tìm ký tự đầu tiên có tần suất 1
        // Duyệt theo thứ tự xuất hiện trong xâu gốc để đảm bảo tính chất "đầu tiên"
        for (char c : s) {
            if (cnt[(unsigned char)c] == 1) {
                cout << c;
                break;
            }
        }
    }
    return 0;
}

• Time Complexity: O(N * L)
• Space Complexity: O(1)

Đây là phiên bản tối ưu của Approach 2. Logic giống nhau nhưng giải thích chi tiết hơn:

• Tận dụng tính chất của bảng mã ASCII để dùng mảng cố định.
• Việc duyệt xâu lần thứ 2 (thay vì duyệt map) giúp đảm bảo lấy được ký tự xuất hiện đầu tiên trong xâu gốc, tránh việc phải xử lý thứ tự từ điển nếu dùng map.
• Độ phức tạp tuyến tính O(N*L) là optimal cho bài toán này.

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

Bài học kinh nghiệm

• Cần phân biệt giữa "ký tự có thứ tự từ điển nhỏ nhất" và "ký tự xuất hiện đầu tiên trong xâu". Các solution sử dụng map sẽ lấy theo thứ tự từ điển (vì map sắp xếp key), còn solution dùng mảng và duyệt lại xâu sẽ lấy theo thứ tự xuất hiện. Đoạn code for(auto i:a) của C++ map mặc định sắp xếp theo key, nhưng for(char c : s) thì theo thứ tự xuất hiện. Đề bài thường yêu cầu thứ tự xuất hiện.
• Việc đếm tần suất là thao tác cơ bản và cần thiết. Kiến trúc dữ liệu phù hợp nhất cho bài toán này là Hash Map (nếu ký tự đa dạng hoặc không xác định phạm vi) hoặc Mảng đếm (nếu phạm vi ký tự nhỏ và cố định, như ASCII).

Lỗi thường gặp

• Lỗi quên khởi tạo lại mảng đếm hoặc map cho mỗi test case mới, dẫn đến sai số cộng dồn.
• Sử dụng cin/cout mặc định trong bài toán lớn có thể gây trễ, cần tắt đồng bộ (ios::sync_with_stdio(false)) và bỏ liên kết với stdio (cin.tie(nullptr)).
• Không xử lý trường hợp không tìm thấy ký tự nào có tần suất 1 (nếu đề bài yêu cầu in ra -1 hoặc ký tự đặc biệt). Các code mẫu trên chỉ in ra khi tìm thấy.