Ký tự K-thống trị

Cho một xâu $s$ gồm các ký tự La-tinh in thường.

Một ký tự $c$ được gọi là $k$-thống trị trong $s$ nếu mọi xâu con liên tiếp của $s$ có độ dài ít nhất $k$ đều chứa ký tự $c$.

Hãy tìm giá trị $k$ nhỏ nhất sao cho tồn tại ít nhất một ký tự $k$-thống trị trong $s$.

Dữ liệu vào

Một dòng duy nhất chứa xâu $s$ gồm các ký tự La-tinh in thường.

Dữ liệu ra

In ra một số nguyên — giá trị $k$ nhỏ nhất cần tìm.

Ràng buộc

• $1\le |s|\le {10}^5$
• $s$ chỉ gồm các ký tự La-tinh in thường.

Ví dụ