Cho chuỗi ký tự \(S\) chỉ gồm các ký tự chữ cái latinh thường \(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à chuỗi có mật độ xuất hiện cao nếu 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à chuỗi mật độ xuất hiện cao vì ký tự \(b\) xuất hiện \(4\) lần, số các ký tự còn lại là \(3\).

Yêu cầu: Tìm một chuỗi con \(X\) của \(S\) là chuỗi có mật độ xuất hiện cao và dài nhất

Dữ liệu vào: chuỗi ký tự \(S\)

Dữ liệu ra: độ dài chuỗi \(X\) tìm được

Input 1

abbbabced

Output 1

7

Input 2

ababab

Output 2

5

Input 3

abc

Output 3

1

Giới hạn

• Có 30% test: Chuỗi \(S\) chỉ gồm các ký \(a, b, c\) và độ dài không quá \(2 \times 10^3\)
• Có 30% test: Chuỗi \(S\) độ dài không quá \(2 \times 10^3\)
• Có 40% test: Chuỗi \(S\) độ dài không quá \(2 \times 10^5\)