Hiểu bài toán

Bài toán yêu cầu đếm số lần xuất hiện của một ký tự x trong chuỗi str. Điểm đặc biệt là bài toán không phân biệt chữ hoa và chữ thường, tức là x và X được coi là giống nhau, và A trong chuỗi cũng được coi là giống a. Đầu vào gồm một chuỗi str, số lượng truy vấn T, và T ký tự cần đếm. Với mỗi ký tự x, ta cần in ra số lần nó xuất hiện trong chuỗi str.

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

Cách Brute Force

#include <stdio.h>
#include <string.h>
#include <ctype.h>

int main() {
    char s[1001];
    fgets(s, 1001, stdin);
    s[strcspn(s, "\n")] = 0; // Xóa ký tự xuống dòng

    int t;
    scanf("%d", &t);
    getchar(); // Đọc ký tự thừa sau số t

    // Chuẩn hóa chuỗi s về dạng lowercase
    for (int i = 0; s[i]; i++) {
        s[i] = tolower(s[i]);
    }

    while (t--) {
        char x;
        scanf(" %c", &x); // Dấu cách trước %c để bỏ qua khoảng trắng/newline
        x = tolower(x);

        int count = 0;
        for (int i = 0; s[i]; i++) {
            if (s[i] == x) {
                count++;
            }
        }
        printf("%d\n", count);
    }
    return 0;
}

• Time Complexity: O(T * N) (N là độ dài chuỗi)
• Space Complexity: O(1)

Phương pháp này xử lý từng truy vấn một. Với mỗi truy vấn, ta duyệt qua toàn bộ chuỗi str để đếm số lần ký tự x xuất hiện. Để đảm bảo không phân biệt hoa thường, ta chuẩn hóa cả chuỗi str và ký tự x về dạng lowercase (hoặc uppercase) trước khi so sánh. Phương pháp này đơn giản và dễ hiểu.

Cách Precomputation (Hashing)

#include <stdio.h>
#include <string.h>
#include <ctype.h>

int main() {
    char s[1001];
    fgets(s, 1001, stdin);
    s[strcspn(s, "\n")] = 0;

    // Mảng đếm tần suất cho 26 chữ cái (a -> z)
    int freq[26] = {0};

    // Đếm tần suất chỉ một lần
    for (int i = 0; s[i]; i++) {
        if (s[i] >= 'A' && s[i] <= 'Z') {
            freq[s[i] - 'A']++; // Chuyển về index 0-25
        } else if (s[i] >= 'a' && s[i] <= 'z') {
            freq[s[i] - 'a']++; // Chuyển về index 0-25
        }
    }

    int t;
    scanf("%d", &t);

    while (t--) {
        char x;
        scanf(" %c", &x);

        int index;
        if (x >= 'A' && x <= 'Z') {
            index = x - 'A';
        } else {
            index = x - 'a';
        }

        printf("%d\n", freq[index]);
    }
    return 0;
}

• Time Complexity: O(N + T)
• Space Complexity: O(1) (Mảng 26 phần tử)

Phương pháp tối ưu hơn bằng cách precompute (tính toán trước) tần suất của các ký tự. Ta chỉ cần duyệt chuỗi str một lần để điền vào mảng freq có 26 phần tử tương ứng với các chữ cái từ 'a' đến 'z'. Sau đó, với mỗi truy vấn, ta chỉ cần lấy giá trị từ mảng tại vị trí tương ứng của ký tự x. Điều này giảm đáng kể thời gian xử lý khi số truy vấn T lớn.

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

Bài học kinh nghiệm

• Chuẩn hóa ký tự (toLowerCase/toUpperCase) là chìa khóa để xử lý yêu cầu 'không phân biệt hoa thường'.
• Precomputation (tính toán trước) giúp giảm độ phức tạp thời gian từ O(T*N) xuống O(N + T) khi số lượng truy vấn lớn.

Lỗi thường gặp

• Quên xử lý ký tự xuống dòng (newline character) khi nhập chuỗi bằng fgets hoặc scanf, dẫn đến lỗi đếm thừa hoặc sai lệch.
• Sử dụng scanf("%c") để đọc ký tự mà không có khoảng trắng trước đó (" %c") có thể đọc nhầm ký tự newline từ lần nhập trước.