# Mật độ xuất hiện cao (HSG Tỉnh Nghệ An 23)

------

Tóm tắt đề: Cho một xâu $S$ có độ dài $length(S)\leq 10^5$, chọn xâu có độ dài lớn nhất sao cho trong đó có một kí tự xuất hiện nhiều hơn tổng số lần xuất hiện của các kí tự khác, in ra chiều dài lớn nhất.

$Subtask$ $1$ : Xâu $S$ chỉ gồm các chữ cái $a$, $b$, $c$. Có độ dài $length(S)\leq 10^3$.

Subtask này cách giải đơn giản của nó chỉ là duyệt các vị trí xuất hiện của $a$, $b$, $c$ và đếm bằng $3$ biến riêng biệt. Độ phức tạp của bạn có thể là $O(n^2)$.

$Subtask$ $2$ : Xâu $S$ gồm tất cả các chữ cái latinh và có chiều dài $length(S)\leq 10^3$.

Subtask này chỉ làm như subtask trên, chỉ có chỗ khác là chúng ta sẽ phải dùng mảng đếm phân phối cộng dồn. Cụ thể:

$Cnt_i,_j$ $=$ $Cnt_{i - 1},_j$ + $(S_i == j)$.

Độ phức tạp của thuật toán sẽ là $O(26 n^2)$.

$Subtask$ $3$ : Xâu $S$ gồm tất cả các chữ cái latinh và có chiều dài $length(S)\leq 10^5$.

Chúng ta với subtask cuối này sẽ rút ra nhận xét như sau:

Với mỗi loại kí tự, duyệt trong xâu $S$, nếu kí tự $S_i$ giống với kí tự cần tìm thì $D_i = 1$ ngược lại $D_i = -1$. Từ đó bài toán trở về bài toán tìm dãy con dài nhất có tổng dương.

Nhận xét thứ hai của chúng ta là sẽ xây dựng một mảng $prefix$ $sum$ để tính tổng và từ đó ta rút ra, nếu đoạn $l - r$ dương thì

$pre_r - pre_{l - 1} > 0$ $=>$ $pre_r > pre_{l - 1}$

Từ đó ta xây dựng thêm một mảng $prefix$ $min$ - mảng min tiền tố để chặt nhị phân trên đó tìm vị trí xa nhất về phía bên trái mà bé hơn $pre_i$ với mỗi $0 < i < length(S)$ trong độ phức tạp $O(n log n)$.

Nhân hai độ phức tạp duyệt với nhau, ta có độ phức tạp $O(26 * n log n)$. Đủ để pass tất cả test.

-----------------