Editorial for Bedao Regular Contest 09 - RIDDLE


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Subtask #1

  • Nhận thấy ~S~ nhỏ nên ta chỉ cần duyệt mọi xâu con trong xâu ~S~, nếu ~S~ là xâu con lí tưởng thì cộng kết quả lên ~1~.
  • Độ phức tạp: ~O(n^3)~

Subtask #2

  • Nhận xét: Giữa ~2~ kí tự giống nhau chỉ tồn tại tối đa ~1~ xâu con lí tưởng. Vì vậy, ta chỉ cần duyệt qua các kí tự từ ~a~ đến ~z~. Nếu giữa 2 kí tự giống nhau gần nhất chỉ có một loại kí tự khác với kí tự đó, cộng kết quả lên ~1~.
  • Độ phức tạp: ~O(26 \times n)~.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.