Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <string>
- #include <algorithm>
- #include <set>
- #include <map>
- #define fi first
- #define se second
- #define pb push_back
- typedef long long ll;
- using namespace std;
- string s;
- bool test(int l, int r, char c) { ///передаем границы подстроки, если передавать строку то оч много памяти уйдет на создание копий
- if (r - l == 1) { ///выход из рекурсии, если длина 1 то просто проверяем что в ней нужный символ
- return (s[l] == c);
- }
- int cnt_c = 0;
- int m = (l + r) / 2;
- for (int i = l; i < m; i++) { ///считаем кол-во букв c в левой половине
- if (s[i] == c) cnt_c++;
- }
- if (cnt_c == m - l) { //если левая из c тогда проверяем что правая c+1 хорошая
- return test(m, r, c+1);
- }
- cnt_c = 0;
- for (int i = m; i < r; i++) { ///считаем кол-во букв c в правой половине
- if (s[i] == c) cnt_c++;
- }
- if (cnt_c == r - m) { //если правая из c тогда проверяем что правая c+1 хорошая
- return test(l, m, c+1);
- }
- return false;
- }
- int main() {
- cin >> s;
- if (test(0, (int)s.size(), 'a')) cout << "YES" << endl;
- else cout << "NO" << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment