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.
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