trang chủ / bài tập / kdomchar

Ký tự K-thống trị

Đề bài

Mô tả

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≤|s|≤105
  • s chỉ gồm các ký tự La-tinh in thường.

Ví dụ

Input Output Giải thích
abacaba 2 Ký tự a xuất hiện ở các vị trí 1,3,5,7. Mọi xâu con độ dài ≥2 đều chứa a, nên k=2.
zzzzz 1 Mọi vị trí đều là z, vậy mọi xâu con độ dài ≥1 đều chứa z.
abcde 3 Không có ký tự nào xuất hiện đủ dày. Với k=3, ký tự c (ở giữa) thoả mãn vì mọi xâu con độ dài ≥3 đều chứa nó.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.400 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.2 gforth 0.7.3 gfortran 12.2.0 go 1.27.0 groovyc 5.1.1 javac 25.0.4 node 26.8.1 julia 1.12.7 kotlinc 2.4.10 lean 4.33.1 sbcl 2.2.9 lua 5.4.9 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.10 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.14.7 racket 8.7 ruby 4.0.6 rustc 1.98.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.3.3 tclsh 8.6 bun 1.4.0 deno 2.9.6 v 0.5.2 zig 0.16.0