Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll; /// Заміняємо long long на ll, бо по-перше, так менше писати, а по-друге я привик писати ll скрізь і тепер просто впадлу виправляти написаний код :)
- int main(){
- ll n; string s;
- cin >> n >> s;
- /**
- По суті, коло означає, що після останнього елемента рядка іде перший.
- Тобто, йдучи по колу, ми будемо нескінченну кількість разів проходити по нашому рядку.
- Але нам не потрібна нескінченність (Бо це трохи довго:) )
- Натомість, помітимо, що відповідь не може бути більшою ніж довжина рядка (Ну бо ти не зможеш обрати підрядок довший, ніж увесь рядок)
- Отже, нам достатньо виписати заданий рядок двічі (Бо таким чином ми зможемо починаючи з кожної позиції рядка побудувати підрядок довжини n)
- **/
- s += s; /// Дописали до кінця радка його ж (Наприклад, "abcd" -> "abcdabcd")
- /**
- Тепер рішаємо задачу не для кола, а для рядка
- Нам тре найти найдовший підрядок такий, шо для кожного <i> : s[i] == s[i-1]+1
- Для кожного символу будемо пробувати дописувати його до найдовшого такого підрядка, який закінчується на попередньому символі.
- **/
- ll answer = 1, current_length = 1;
- for (ll i=1; i<s.length(); i++){
- if (s[i] == char(s[i-1] + 1)) current_length ++; /// Якщо можемо дописати - довжина ++
- else current_length = 1; /// Інакше довжина знову 1
- answer = max(answer, current_length);
- }
- cout << answer << '\n';
- return 0;
- }
Add Comment
Please, Sign In to add comment