Mật độ xuất hiện cao (HSG9 NA 2023)

Điểm: 1700 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 1G

Input: MATDO.inp

Output: MATDO.out

Tác giả:

Sunlight

Dạng bài

Trò chơi chọn bóng mà nhóm của Tuấn thiết kế được bạn bè và giáo viên trong trường đánh giá rất cao. Sau thành công này, Tuấn cùng nhóm bạn tập trung học tập để thi vào lớp chuyên tin của một trường chuyên danh giá trong tỉnh. Những bài tập mà Tuấn làm đều yêu cầu kỹ năng thiết kế thuật toán chuyên nghiệp. Một trong các bài tập mà bạn ấy đang xây dựng thuật toán có nội dung như sau:

Cho chuỗi kí tự $S$ chỉ gồm các kí tự chữ cái latinh thường từ a, ..., z. Một chuỗi con $X$ (gồm các kí tự ở vị trí liên tiếp) của $S$ được gọi là một chuỗi có mật độ xuất hiện cao nếu trong chuỗi $X$ có một kí tự mà số lần xuất hiện của kí tự đó nhiều hơn số các kí tự còn lại trong chuỗi $X$ .

Ví dụ, chuỗi $S=$ abbbabced, chuỗi con $X=$ abbbabc là một chuỗi có mật độ xuất hiện cao, vì có kí tự b xuất hiện $4$ lần, số các kí tự còn lại là $3$ . Nếu $X=$ abbbabce, kí tự xuất hiện nhiều lần nhất $4$ lần (kí tự b) và số kí tự còn lại là $4$ . Do vậy chuỗi $X=$ abbbabce không phải là một chuỗi có mật độ xuất hiện cao.

Yêu cầu: Tìm một chuỗi con $X$ (gồm các kí tự ở vị trí liên tiếp) của $S$ là một chuỗi có mật độ xuất hiện cao và độ dài lớn nhất.

Tuấn cũng đã có thuật toán của mình, còn bạn thì sao? Hãy lập trình giải bài toán trên để đối chiếu kết quả nhé.

Input, Output và Subtasks

Input: (MatDo.inp)

Gồm một chuỗi kí tự $S$ chỉ gồm các kí tự chữ cái latinh thường và có độ dài không lớn hơn $2\times 10^5$ .

Output: (MatDo.out)

Gồm một số nguyên duy nhất là độ dài của chuỗi $X$ tìm được.

Subtasks

Có $30\%$ số test ứng với $30\%$ số điểm thỏa mãn:
Chuỗi $S$ chỉ gồm các kí tự thuốc tập $3$ kí tự $\{$ a $,$ b $,$ c $\}$ và độ dài chuỗi $S$ không quá $2\times 10^5$ .
Có $30\%$ số test ứng với $30\%$ số điểm thỏa mãn:
Chuỗi $S$ chỉ gồm các kí tự chữ cái latinh thường và độ dài chuỗi $S$ không quá $2\times 10^3$ .
Có $40\%$ số test ứng với $40\%$ số điểm thỏa mãn:
Chuỗi $S$ chỉ gồm các kí tự chữ cái latinh thường và độ dài chuỗi $S$ không quá $2\times 10^5$ .

Sample

Input (MatDo.inp)

abbbabced

Output (MatDo.out)

Notes

Ta có thể chọn chuỗi $X$ thỏa mãn là:
$X=$ abbbabc hoặc $X=$ bbbabce.

Sample

Input (MatDo.inp)

ababab

Output (MatDo.out)

Notes

Ta có thể chọn chuỗi $X$ thỏa mãn là:
$X=$ ababa vì kí tự a xuất hiện $3$ lần, số các kí tự còn lại là $2$ .
hoặc $X=$ babab vì kí tự b xuất hiện $3$ lần, số các kí tự còn lại là $2$ .

Sample

Input (MatDo.inp)

abc

Output (MatDo.out)

Notes

Ta có thể chọn chuỗi $X$ thỏa mãn là:
$X=$ a vì kí tự a xuất hiện $1$ lần, số các kí tự còn lại là $0$ .
hoặc $X=$ b, $X=$ c đều thỏa mãn.

Bình luận

Không có bình luận nào.