Hiểu bài toán

Bài toán yêu cầu tìm số lượng ký tự khác nhau tối thiểu cần thêm vào để tạo ra tên thuốc S. Quy tắc là: thêm một ký tự mới (chưa có trong tên thuốc hiện tại) sẽ làm mất 1 năm tuổi, trong khi sử dụng ký tự đã có sẵn thì không tốn kém. Vì vậy, để giảm tuổi tác ít nhất, ta cần tối thiểu hóa số lần thêm ký tự mới. Điều này có nghĩa là: với mỗi ký tự khác nhau trong chuỗi S, ta chỉ cần thêm nó một lần đầu tiên, những lần sau có thể dùng lại. Do đó, đáp án chính là số lượng ký tự khác nhau trong chuỗi S.

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

Cách Sử dụng mảng đánh dấu (Boolean Array)

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    getline(cin,s);
    bool use[26]={false};
    int cnt=0;
    for(char c:s){
        int idx=c-'a';
        if(!use[idx]){
            use[idx]=true;
            cnt++;
        }

    }
    cout<<cnt;

}

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

Phương pháp này sử dụng một mảng boolean use có kích thước cố định 26 (tương ứng với 26 chữ cái tiếng Anh) để theo dõi các ký tự đã xuất hiện. Ta duyệt qua từng ký tự trong chuỗi S, chuyển đổi ký tự thành chỉ số từ 0 đến 25. Nếu chỉ số đó chưa được đánh dấu (false), ta đánh dấu nó là true và tăng biến đếm cnt. Biến cnt cuối cùng chính là số lượng ký tự khác nhau, cũng là số năm tuổi bị mất.

Cách Sử dụng tập hợp (Set)

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin >> s;
    set<char> st;
    for (char c : s) st.insert(c);
    cout << st.size();
    return 0;
}

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

Phương pháp này sử dụng cấu trúc dữ liệu set của C++. Khi thêm các ký tự của chuỗi S vào set, set sẽ tự động loại bỏ các phần tử trùng lặp, chỉ giữ lại các ký tự duy nhất. Sau đó, kích thước của set (st.size()) chính là số lượng ký tự khác nhau. Độ phức tạp thời gian là O(n log n) do mỗi thao tác chèn vào set mất O(log n).

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

Bài học kinh nghiệm

• Để giảm tuổi tác ít nhất, ta chỉ cần thêm mỗi ký tự khác nhau trong S đúng một lần.
• Số năm tuổi bị mất chính bằng số lượng ký tự khác nhau (ký tự duy nhất) trong chuỗi S.
• Bài toán quy về bài toán đếm số lượng ký tự xuất hiện ít nhất một lần trong chuỗi.

Lỗi thường gặp

• Sai lầm khi nghĩ rằng cần phải đếm số lần xuất hiện của từng ký tự thay vì chỉ đếm số loại ký tự.
• Quên xử lý trường hợp chuỗi rỗng (dù đề bài cho độ dài tối đa 100, nhưng logic vẫn phải đúng).
• Cẩn thận với ký tự khoảng trắng nếu sử dụng getline thay vì cin >> string.