Сміх#153

Сміх (Розбір)

«Сміх» — це підрядок, у якому чергуються літери a та h, тобто будь-які два сусідні символи різні й обидва належать множині .

Тому задача розв'язується одним проходом зі лічильником поточної довжини.

Ідемо по рядку і для кожного символу:

  • якщо це не a і не h, ланцюжок обривається — обнуляємо лічильник;

  • якщо це a або h, але він збігається з попереднім символом, чергування порушено — новий ланцюжок починається саме з цього символу, тому лічильник стає рівним одиниці;

  • інакше чергування триває — збільшуємо лічильник на одиницю.

Після кожного кроку оновлюємо відповідь максимумом лічильника.

Зверніть увагу на другий випадок: після hh лічильник не обнуляється повністю, адже друга h сама по собі вже є коректним сміхом довжини . Саме тут найлегше помилитися.

Складність — , зберігати весь рядок необов'язково.