Subtask 1: ~O(2^n \times n)~.

Ta duyệt quay lui để xem loại phần tử nào và giữ lại phần tử nào. Sau đó kiểm tra điều kiện trong ~O(n)~.

Subtask 2: ~O(n)~.

Xét xâu ~s~ có hai phần tử đầu là ab. Ta luôn suy ra được phần tử thứ ~i~ ~(i \ge 2)~ của ~s~ là ~1 - s[i - 2]~. Sau khi biết được toàn bộ xâu ~s~, ta có thể tham lam để chọn ra tiền tố lớn nhất của xâu ~s~ là xâu con của xâu nhị phân ban đầu. Vì chỉ có ~4~ khả năng của ab nên ta sẽ làm tham lam ~4~ lần.

Code mẫu

#include <bits/stdc++.h>
using namespace std;
#define print_op(...) ostream& operator<<(ostream& out, const __VA_ARGS__& u)
#define db(val) "["#val" = "<<(val)<<"] "
#define CONCAT_(x, y) x##y
#define CONCAT(x, y) CONCAT_(x, y)
#ifdef LOCAL   
#   define clog cerr << setw(__db_level * 2) << setfill(' ') << "" << setw(0)
#   define DB() debug_block CONCAT(dbbl, __LINE__)
    int __db_level = 0;
    struct debug_block {
        debug_block() { clog << "{" << endl; ++__db_level; }
        ~debug_block() { --__db_level; clog << "}" << endl; }
    };
#else
#   define clog if (0) cerr
#   define DB(...)
#endif
template<class U, class V> print_op(pair<U, V>) {
    return out << "(" << u.first << ", " << u.second << ")";
}
template<class Con, class = decltype(begin(declval<Con>()))>
typename enable_if<!is_same<Con, string>::value, ostream&>::type
operator<<(ostream& out, const Con& con) { 
    out << "{";
    for (auto beg = con.begin(), it = beg; it != con.end(); ++it)
        out << (it == beg ? "" : ", ") << *it;
    return out << "}";
}
template<size_t i, class T> ostream& print_tuple_utils(ostream& out, const T& tup) {
    if constexpr(i == tuple_size<T>::value) return out << ")"; 
    else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); 
}
template<class ...U> print_op(tuple<U...>) {
    return print_tuple_utils<0, tuple<U...>>(out, u);
}


string res;
int ans = 0;

void solve(string& a, vector<char> b) {
    while (b.size() < a.size()) {
        assert(b.size() >= 2);
        b.push_back('1' + '0' - b[(int)b.size() - 2]);
    }
    int run = 0;
    for (int i = 0; i < (int)a.size(); ++ i) {
        if (run < (int)b.size() && a[i] == b[run]) {
            ++ run;
        }
    }
    if (ans < run) {
        ans = run;
        res = ""; 
        for (int i = 0; i < run; ++ i) {
            res += b[i];
        }
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    string a;
    cin >> a;
    solve(a, {'0', '0'});
    solve(a, {'0', '1'});
    solve(a, {'1', '0'});
    solve(a, {'1', '1'});
    cout << res;
}