Tóm tắt đề

• Cho một xâu ký tự gồm chữ thường và khoảng trắng có độ dài không quá $10^{6}$ kí tự.
• Tìm từ có số lượng ký tự khác nhau nhiều nhất trong xâu và in ra từ đó (Một "từ" là dãy liên tiếp không chứa khoảng trắng).

Giới hạn đề bài

• Subtask 1: Có 50% test: độ dài xâu không quá $10^{3}$ và không có dấu trắng ở đầu và cuối xâu đồng thời ở giữa hai từ chỉ có đúng 1 khoảng trắng;
• Subtask 2: Có 50% số test: không có ràng buộc gì thêm.

Lời giải

Subtask 1: Độ dài xâu không quá $10^{3}$ và không có dấu trắng ở đầu và cuối xâu đồng thời ở giữa hai từ chỉ có đúng 1 khoảng trắng;

Tiếp cận

Dùng mảng đánh dấu để kiểm tra các ký tự khác nhau.

Thực hiện

Duyệt qua từng từ trong xâu đầu vào, với mỗi từ, ta dùng mảng đánh dấu để kiểm tra các ký tự khác nhau. So sánh số ký tự khác nhau của từ hiện tại với kết quả hiện tại, nếu lớn hơn thì cập nhật. Sau cùng in ra từ có số lượng ký tự khác nhau nhiều nhất.

Độ phức tạp

$O(n)$.

Subtask 2: Như đề bài mô tả

Tiếp cận

Ý tưởng giống subtask 1 nhưng xâu đầu vào chưa được chuẩn hóa nên ta lưu ý cần chuẩn hóa xâu.

Thực hiện

Như trên.

Độ phức tạp

$O(n)$.