算法
(贪心) $O(N)$
首先,如果 $S$ 的字典序比 atcoder
大的话,那么显然不需要操作
其次,如果 $S$ 仅包含 a
的话,自然也无法让它比 atcoder
的字典序大
最后考虑其余的一般情况:
可以考虑贪心,即找到 $S$ 的最左边第一个不为 a
的位置,然后将其对应的字符不断往左边交换直到当前交换后的 $S$ 的字典序大于 atcoder
才停止
C++ 代码
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::string;
const string a = "atcoder";
void solve() {
string s;
cin >> s;
if (s > a) {
puts("0");
return;
}
int n = s.size();
if (s == string(n, 'a')) {
puts("-1");
return;
}
int k = 0;
while (s[k] == 'a') ++k;
int ans = 0;
while (s <= a) {
std::swap(s[k], s[k-1]);
--k;
ans++;
}
cout << ans << '\n';
}
int main() {
int t;
cin >> t;
while (t--) solve();
return 0;
}