int solve(const string& s) {
    vector<int> dp(s.size());
    for (char c = 'y'; c >= 'a'; --c) {
        vector<int> idx;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] >= c) {
                idx.push_back(i);
            }
        }
        if (idx.empty()) {
            continue;
        }
        vector<int> blocks;
        for (int i = 0; i + 1 < idx.size(); ++i) {
            if (s[idx[i]] == c && s[idx[i + 1]] > c) {
                blocks.push_back(i + 1);
            }
        }
        if (s[idx[0]] > c && s[idx[idx.size() - 1]] == c) {
            blocks.push_back(0);
        }
        if (blocks.empty()) {
            continue;
        }
        vector<int> pre(blocks.size());
        pre[0] = numeric_limits<int>::max() / 2;
        for (int i = 1; i < blocks.size(); ++i) {
            pre[i] = min(pre[i - 1], dp[idx[blocks[i - 1]]]);
        }
        vector<int> suf(blocks.size());
        suf[blocks.size() - 1] = numeric_limits<int>::max() / 2;
        for (int i = (int)blocks.size() - 2; i >= 0; --i) {
            suf[i] = min(suf[i + 1], dp[idx[blocks[i + 1]]]);
        }
        vector<int> dpn(s.size());
        for (int i = 0; i < blocks.size(); ++i) {
            int x = min(pre[i], suf[i]) + blocks.size() - 1;
            int j = (blocks[i] + idx.size() - 1) % idx.size();
            for (; s[idx[(j + idx.size() - 1) % idx.size()]] == c; j = (j + idx.size() - 1) % idx.size()) {
                dpn[idx[j]] = min<int>(dp[idx[blocks[i]]] + blocks.size(), x + 1);
            }
            dpn[idx[j]] = min<int>(dp[idx[blocks[i]]] + (blocks.size() == 1 ? 0 : blocks.size()), x);
        }
        int x = min(dp[idx[blocks[0]]], suf[0]) + blocks.size();
        for (int i = 0; i < idx.size(); ++i) {
            if (s[idx[i]] > c) {
                dpn[idx[i]] = x;
            }
        }
        dp = move(dpn);
    }
    return dp[0];
}