Masala #N6OZWKOG82
Fruits (Mevalar)
Gavhar o’zining super bog’idan \(N\) dona meva terib oldi va bir qatorga terib chiqdi. Har bir meva bu yoki Apelsin yoki Banan. Gavharga apelsin ko’proq yoqadi, shuning uchun u shunday mevalar oralig’ini tanlamoqchiki, bunda chapdan kelganda ham, o’ngdan kelganda ham Apelsinlar soni har doim Bananlar sonidan kam bo’lmasligi kerak.
Bunday oraliqlar ichidan Gavhar uzunligi maksimalini tanlamoqchi. Siz unga yordam bering!
Birinchi qatorda sizga \(N\) soni beriladi, mevalar soni.
Ikkinchi qatorda uzunligi \(N\)ga teng \(S\) satr. Bunda har bir element yoki \(a\) (apelsin),
yoki \(b\) (banan)ga teng.
Chegaralar
• \(1 ≤ N ≤ 10^6\)
• \(S\) satr faqat \(A\) va \(B\) belgilaridan tashkil topgan
Subtasklar
1. (11 ball) \(N ≤ 300\)
2. (17 ball) \(N ≤ 2000\)
3. (19 ball) \(N ≤ 5000\)
4. (10 ball) \(N ≤ 10^5\) , shuningek avval faqat apelsinlar, keyin faqat bananlar, va so’ngida faqat apelsinlar bor.
5. (22 ball) \(N ≤ 10^5\)
6. (21 ball) Qo’shimcha chegaralarsiz
Yagona qatorda eng uzun oraliqning uzunligini chiqaring.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
8 baaababb |
5 |
Masalan, N = 8 va S = “baaababb” bo’lsin. Biz S[2...6] = “aaaba” oraliqni tanlashimiz mumkin.
Chapdan o’ngga kelganimizda satr “aaaba” bo’ladi.
Bunda “a”, “aa”, “aaa”, “aaab” va “aaaba” satrlarning har birida “a”lar soni “b”lar sonidan kam emas.
O’ngdan chapga kelganimizda satr “abaaa” bo’ladi.
Bunda “a”, “ab”, “aba”, “abaa” va “abaaa” satrlarning har birida “a”lar soni “b”lar sonidan kam emas.
Telegram kanalimizga obuna bo'ling