Editorial for nhatchu: Robot nhặt chữ

Hiểu bài toán

Xác định xâu ký tự mà Robot sẽ nhặt dựa trên quy tắc: Robot đi qua từng ký tự từ đầu đến cuối hàng chữ cái. Nếu Robot chưa từng nhặt ký tự đó trước đó, nó sẽ nhặt ký tự đó và thêm vào xâu kết quả. Nếu nó đã nhặt ký tự đó rồi, nó sẽ bỏ qua. Nhiệm vụ là in ra xâu các ký tự được nhặt theo đúng thứ tự chúng xuất hiện lần đầu tiên.

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

Cách Hash Set / Mảng đánh dấu

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

int main() {
    char s[100005];
    if (fgets(s, sizeof(s), stdin) == NULL) return 0;

    // Xóa ký tự newline nếu có
    size_t len = strlen(s);
    if (len > 0 && s[len-1] == '\n') {
        s[len-1] = '\0';
        len--;
    }

    int seen[256] = {0}; // Mảng đánh dấu cho tất cả ký tự ASCII
    char out[100005];
    int k = 0;

    for (int i = 0; i < len; i++) {
        unsigned char c = s[i];
        if (seen[c] == 0) {
            out[k++] = s[i];
            seen[c] = 1;
        }
    }
    out[k] = '\0';
    printf("%s", out);
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(1) (mảng 256 phần tử)

Sử dụng một mảng seen với 256 vị trí (độ dài của bảng mã ASCII) để theo dõi các ký tự đã xuất hiện. Mỗi khi duyệt qua một ký tự s[i], ta kiểm tra giá trị tại chỉ số seen[s[i]]. Nếu bằng 0, tức là ký tự này chưa xuất hiện, ta thêm nó vào xâu kết quả và đánh dấu seen[s[i]] = 1. Cách này rất nhanh và hiệu quả về bộ nhớ.

Cách In trực tiếp khi duyệt

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

int main() {
    char s[100001];
    if (scanf("%s", s) != 1) return 0;

    int c[256] = {0};
    int len = strlen(s);

    for (int i = 0; i < len; i++) {
        if (c[s[i]] == 0) {
            printf("%c", s[i]);
            c[s[i]]++;
        }
    }
    return 0;
}

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

Đây là biến thể của cách tiếp cận đầu tiên nhưng tối ưu hơn một chút về bộ nhớ ở khâu output. Thay vì lưu các ký tự đã nhặt vào một mảng out riêng rồi in sau, chương trình in ngay lập tức ký tự đó ra màn hình khi nó được phát hiện là lần xuất hiện đầu tiên. Điều này giúp tránh việc phải quản lý một chuỗi output bổ sung.

Cách Duyệt với độ dài chuỗi động

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <stdbool.h>
#include <stdlib.h>

int main(){
    char a[100000];
    scanf("%s",a);
    int dp[256]={0};
    for(int i=0; i<strlen(a); i++){
        if(dp[(int)a[i]]!=1){
            printf("%c",a[i]);
            dp[(int)a[i]]=1;
        }
    }
}

• Time Complexity: O(n^2) (nếu strlen tính lại mỗi lần), O(n) (nếu tối ưu)
• Space Complexity: O(1)

Mã nguồn này sử dụng logic tương tự như các cách trên (mảng đánh dấu 256 phần tử). Tuy nhiên, có một điểm cần lưu ý trong vòng lặp for: việc gọi strlen(a) ở mỗi lần lặp có thể khiến độ phức tạp tăng lên O(n^2) nếu trình biên dịch không tối ưu. Tuy nhiên, về cơ bản thuật toán vẫn là tìm ký tự đầu tiên xuất hiện.

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

Bài học kinh nghiệm

• Bài toán có thể được giải quyết bằng việc theo dõi trạng thái của các ký tự (đã xuất hiện hay chưa).
• Vì tập hợp ký tự đầu vào chỉ gồm các chữ cái Latinh, ta có thể sử dụng một mảng 256 phần tử (tương ứng với bảng mã ASCII) làm bảng băm (hash table) để lưu trạng thái một cách hiệu quả O(1).

Lỗi thường gặp

• Lỗi nhập/xuất: Nếu dùng scanf để nhập xâu có thể bị lỗi khi có khoảng trắng, nên dùng fgets là an toàn hơn. Tuy nhiên, fgets thường đọc cả ký tự newline, cần loại bỏ nó trước khi xử lý.
• Quên kiểm tra biên hoặc khai báo mảng quá nhỏ so với giới hạn đề bài (10^5).