题意简述

给定一个长度为 $n$ 的字符串 $s$。

一次操作中，我们必须选择当前字符串的字典序最大子序列，然后将这个子序列循环右移一次。

要求最少操作多少次才能让整个字符串变成非递减有序；如果无论如何都做不到，则输出 $-1$。

核心观察

设当前字符串的字典序最大子序列下标为：

$$p_1 < p_2 < \dots < p_k$$

对应字符为：

$$c_1, c_2, \dots, c_k$$

那么一定有：

$$c_1 \ge c_2 \ge \dots \ge c_k$$

也就是说，这个子序列中的字符一定是一个单调不升序列。

这是因为如果后面出现了更大的字符，那么前面那个更小的字符就不该被保留在“字典序最大子序列”中。

如何构造这个最大子序列

标程用一个栈式结构 subset 来维护这个子序列：

for (int i = 1; i <= n; ++i)
{
    while (!subset.empty() && s[subset.back()] < s[i])
    {
        subset.pop_back();
    }
    subset.push_back(i);
}

它的含义是：

• 从左到右扫描字符串；
• 如果当前字符 $s_i$ 比栈顶对应字符更大，那么栈顶那个位置就不可能出现在字典序最大子序列中，直接弹出；
• 最后保留下来的这些位置，就是字典序最大子序列的位置。

等价地说，这个子序列恰好由所有“后缀最大值位置”组成。

操作最终等价于什么

这是本题最关键的一步。

假设初始字典序最大子序列对应的字符是：

$$c_1,c_2,\dots,c_k$$

由于它单调不升，我们不断执行题目规定的操作，最终效果等价于：

把这段子序列反转后，再放回原来的这些位置上。

也就是说，最终这些位置上的字符会变成：

$$c_k,c_{k-1},\dots,c_1$$

因此，整道题实际上可以转化为：

1. 找出初始字符串的字典序最大子序列；
2. 把这段子序列直接反转；
3. 检查整个字符串是否已经变成非递减；
4. 如果不能，则答案是 $-1$；
5. 如果可以，再计算最少需要多少次操作。

这也正是标程所做的事情。

为什么反转后还要检查是否有序

注意，操作只能影响这一个特殊子序列上的字符，其余位置的字符顺序完全不变。

因此，如果把这段子序列反转之后，整个字符串仍然不是非递减的，那么说明无论怎么操作，都不可能把整个字符串排好序。

所以标程在反转后做了这样一段判断：

for (int i = 2; i <= n; ++i)
{
    if (s[i] < s[i - 1])
    {
        ans = -1;
        break;
    }
}

只要发现有某个位置不满足：

$$s_i \ge s_{i-1}$$

就直接输出 $-1$。

最少操作次数如何计算

设这个最大子序列长度为 $k$。

如果我们把它完整反转，那么看起来似乎需要 $k-1$ 次循环右移。但实际上，开头那一段与首字符相同的前缀不会产生额外贡献。

设最大子序列最前面连续相等的字符个数为 $cnt$，也就是：

$$c_1=c_2=\dots=c_{cnt}$$

并且如果 $cnt<k$，那么：

$$c_{cnt} > c_{cnt+1}$$

那么答案就是：

$$k-cnt$$

标程中对应的实现是：

int ans = 0;
int m = (int)subset.size() - 1;
while (ans <= m && s[subset[ans]] == s[subset[0]])
{
    ans++;
}
ans = m - ans + 1;

这里：

• subset.size() 就是 $k$；
• 前面的 while 在统计前缀连续等于首字符的个数 $cnt$；
• 最终：

$$ans = k-cnt$$

为什么是这个值？

因为前面这些相同的最大字符在循环移动过程中彼此交换并不会改变字符串，因此不需要单独计入操作数；真正需要“推进”的，只有后面那些严格更小的字符。

正确性说明

性质 $1$

字典序最大子序列一定是所有后缀最大值位置组成的序列，因此它的字符序列一定单调不升。

性质 $2$

题目规定的操作是确定的。对于这条单调不升的最大子序列，反复执行操作，最终唯一可能到达的目标状态就是把它反转后放回原位置。

性质 $3$

如果把这条子序列反转后，整个字符串仍然不是非递减，那么说明仅靠这种操作无法改变其他字符之间的相对关系，因此答案只能是 $-1$。

性质 $4$

若反转后可以得到有序串，那么真正需要的操作次数正好等于最大子序列长度减去其开头连续相同字符的个数，即：

$$k-cnt$$

综上，算法输出的答案是正确的。

标程解释

完整标程如下：

#include <bits/stdc++.h> 
using namespace std;
int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int q;
    cin >> q;
    while (q--)
    {
        int n;
        string s;
        cin >> n >> s;
        s = '$' + s;
        vector<int> subset;
        for (int i = 1; i <= n; ++i)
        {
            while (!subset.empty() && s[subset.back()] < s[i])
            {
                subset.pop_back();
            }
            subset.push_back(i);
        }
        int ans = 0;
        int m = (int)subset.size() - 1;
        while (ans <= m && s[subset[ans]] == s[subset[0]])
        {
            ans++;
        }
        ans = m - ans + 1;

        for (int i = 0; i <= m; ++i)
        {
            if (i < m - i)
            {
                swap(s[subset[i]], s[subset[m - i]]);
            }
        }
        for (int i = 2; i <= n; ++i)
        {
            if (s[i] < s[i - 1])
            {
                ans = -1;
                break;
            }
        }
        cout << ans << '\n';
    }
}

代码流程可以概括为：

1. 读入字符串；
2. 用单调栈求出字典序最大子序列的位置；
3. 统计这个子序列前面连续等于首字符的个数；
4. 直接把这条子序列反转；
5. 检查整个字符串是否已经有序；
6. 如果有序，输出 $k-cnt$；否则输出 $-1$。

复杂度分析

每个字符至多进栈、出栈各一次，因此求最大子序列是线性的。

后续反转和检查是否有序也都是线性的。

所以每组测试数据的时间复杂度为：

$$O(n)$$

空间复杂度为：

$$O(n)$$

而所有测试数据的字符串总长度不超过：

$$2 \cdot 10^5$$