Hiểu bài toán

Bài toán yêu cầu đếm và in ra số lần xuất hiện của các ký tự chữ (a-z, A-Z) trong một chuỗi được nhập vào. Các ký tự khác như số, khoảng trắng hay ký tự đặc biệt phải bị bỏ qua. Kết quả cần được in ra theo thứ tự tự nhiên (theo mẫu code là thứ tự xuất hiện trong bảng ASCII/độ ưu tiên của map), mỗi dòng là một ký tự và số lần nó xuất hiện dưới dạng 'ký tự:số_lần'. Nếu chuỗi không chứa ký tự chữ nào, chương trình không in ra bất cứ thứ gì.

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

Cách Sử dụng std::map (Associative Array)

#include <iostream>
#include <string>
#include <map>
#include <cctype>

int main() {
    std::string s;
    std::getline(std::cin, s);
    std::map<char, int> counts;

    for (char c : s) {
        if (isalpha(c)) {
            counts[c]++;
        }
    }

    if (!counts.empty()) {
        for (const auto& pair : counts) {
            std::cout << pair.first << ":" << pair.second << std::endl;
        }
    }
    return 0;
}

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

Phương pháp này sử dụng std::map để lưu trữ tần suất của mỗi ký tự. Map là một cấu trúc dữ liệu cây đỏ-đen, tự động sắp xếp các key (ở đây là ký tự) theo thứ tự tăng dần. Khi duyệt qua chuỗi đầu vào, ta kiểm tra từng ký tự bằng hàm isalpha. Nếu là chữ cái, ta cập nhật số đếm trong map. Cuối cùng, duyệt qua map để in kết quả. Cách này rất tiện lợi vì tự động sắp xếp và xử lý việc lưu trữ động.

Cách Mảng đếm (Frequency Array)

#include <iostream>
#include <string>
#include <vector>

int main() {
    std::string s;
    std::getline(std::cin, s);
    std::vector<int> cnt(26, 0); // Mảng cho a-z

    for (char c : s) {
        if (c >= 'a' && c <= 'z') {
            cnt[c - 'a']++;
        }
    }

    for (int i = 0; i < 26; i++) {
        if (cnt[i] > 0) {
            std::cout << (char)(i + 'a') << ":" << cnt[i] << std::endl;
        }
    }
    return 0;
}

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

Đây là phương pháp tối ưu nhất về mặt tốc độ. Ta sử dụng một mảng cố định kích thước 26 (giả sử chỉ xử lý chữ cái thường) để lưu trữ số đếm. Chỉ số của mảng được tính bằng cách lấy mã ASCII của ký tự trừ đi mã ASCII của 'a'. Việc truy cập và cập nhật mảng là hằng số O(1). Đầu ra sẽ mặc định theo thứ tự từ a đến z.

Cách Sử dụng std::unordered_map

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
#include <algorithm>

int main() {
    std::string s;
    std::getline(std::cin, s);
    std::unordered_map<char, int> counts;

    for (char c : s) {
        if (std::isalpha(c)) {
            counts[c]++;
        }
    }

    // Chuyển key vào vector để sort trước khi in
    std::vector<char> keys;
    for (auto const& [key, val] : counts) {
        keys.push_back(key);
    }
    std::sort(keys.begin(), keys.end());

    for (char key : keys) {
        std::cout << key << ":" << counts[key] << std::endl;
    }
    return 0;
}

• Time Complexity: O(N + K log K)
• Space Complexity: O(K)

Cách này sử dụng std::unordered_map để lưu trữ, giúp việc cập nhật tần suất nhanh hơn (O(1) trung bình) so với map. Tuy nhiên, unordered_map không giữ thứ tự, nên để in ra theo thứ tự tự nhiên như yêu cầu (hoặc theo mẫu), ta phải dùng thêm một vector để lưu các key rồi sort trước khi in.

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

Bài học kinh nghiệm

• Sử dụng hàm isalpha() hoặc kiểm tra khoảng ASCII ('a' <= c <= 'z') để lọc ký tự.
• Vấn đề yêu cầu chỉ in các ký tự chữ, không tính khoảng trắng hay số.
• Khi dùng std::getline để đọc toàn bộ dòng, ta có thể xử lý cả các khoảng trắng nằm giữa các từ.

Lỗi thường gặp

• Quên nhập/xử lý các khoảng trắng trong chuỗi input (ví dụ: nhập 'a b' thay vì 'ab'). Dùng cin >> s chỉ đọc được đến khoảng trắng đầu tiên, cần dùng getline.
• Chỉ xử lý chữ cái hoa hoặc thư mà quên mất bộ chữ cái còn lại (ví dụ code chỉ xử lý 'a'-'z' nhưng input có 'A'-'Z').
• In ra kết quả ngay cả khi không có ký tự chữ nào (vi phạm điều kiện 'Nếu Không có kí tự chữ thì ko in ra cái gì hết').