Tóm tắt đề bài

Cho xâu ~s~, tìm xâu con liên tiếp dài nhất mà có một giá trị thống trị.

Giá trị thống trị là giá trị (trong bài này là ký tự) xuất hiện nhiều hơn tổng số lần xuất hiện của các giá trị khác.

Giới hạn: ~|s| \le 200000~.

Subtask 1 + 2. ~|s| \le 2000~

Với mỗi đoạn con ~s[i, j]~ trong xâu ~s~, ta sẽ dùng mảng cộng dồn tương ứng của ~26~ ký tự để tìm xem có ký tự nào thống trị không.

Độ phức tạp: ~O~ (~|s|^2 \times 26~).

Subtask 3. ~|s| \le 200000~

Ta sẽ thử duyệt cố định ~26~ ký tự thống trị. Lúc này, ta gọi mảng ~a_i = 1~ nếu ~s_i~ là ký tự ta đang thử, và ~a_i = -1~ nếu ~s_i~ không là ký tự ta đang thử.

Lúc này, một đoạn con ~s[l, r]~ là thỏa mãn nếu tổng của đoạn con này dương. Bài toán trở thàn tìm đoạn con dài nhất có tổng dương. Điều này có thể thực hiện bằng tổng tiền tố như trên.

Độ phức tạp: ~O~ (~|s| \times 26~) hoặc ~O~ (~|s| \times 26 \times log~ ~|s|~), tùy cách cài đặt.