Hướng dẫn cho Kaninho tập đếm với xâu

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: cuom1999

Hint 1: Với mỗi \(i\), hãy tìm \(j\) lớn nhất mà \(S[i..j]\) thỏa mãn điều kiện đề bài.

Hint 2: Có thể tìm được \(j\) bằng cách nào?

Hint 3: Làm sao để kiểm tra \(S[i..j]\) thỏa mãn điều kiện?

Lời giải:

Chúng ta sẽ dùng kỹ thuật 2 con trỏ để xử lý bài toán này. Hai con trỏ \(i, j\) sẽ lưu vị trí mà \(S[i..j]\) thỏa mãn điều kiện. Trong quá trình di chuyển hai con trỏ, cần lưu mảng \(cnt[a..z]\) là số lần xuất hiện của mỗi ký tự trong xâu con hiện tại.

Đô phức tạp: \(O(n)\)


Bình luận