https://www.hackerrank.com/contests/w28/challenges/suffix-rotation/problem

首先最后一定是能排成从小到大的，且每次一定是把最小的字符往前移。

而且无论如何移动前i个字符，第i+1之后的字符在环上的相对位置一定是不变的。

那么当第i个字符最后一位确定了之后，后面的字符串一定是固定的。

用$dp[j]$表示排完前$i(i=s[j])$个字符，最后一位为$j$的最小步数。

考虑从第$i-1$个字符到第$i$个字符的过程，每一块连续的$i$都是一起移动的，而且每次都是把一个块的开头移动到前面。

所以说$dp[j]$的意思更正为最后一块为$j$。(可以让每个块用开头代表)

考虑每个第$i-1$个字符的最后一块$k$的贡献,

定义$next[k]$为删去前$i-1$个字符后块$k$后面的第一个位置,$cnt[i]$为字符$i$的块的个数。

若$s[next[k]]!=i$，则对任意$j,dp[j]=dp[k]+cnt[i]$

若$s[next[k]]=i$，

设$next[k]$所属的块为$j'$

(1)若$next[k]$不是$j'$的块首，那么同上

(2)若$next[k]$是$j'$块首

对$j!=j'$,因为块$j'$不需要移动,所以$dp[j]=dp[k]+cnt[i]-1$

对$j'$，若$cnt[i]>1$，则其他$j$必须先移动，所以$j'$仍需要移动，所以$dp[j']=dp[k]+cnt[i]$;

          若$cnt[i]=1$，则$dp[j']=dp[k]$

记个最小值就$O(n)$了

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define pb push_back
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)

template <typename T> inline void chmin(T &x,const T &y)
{
    if(x>y)x=y;
}
template <typename T> inline void chmax(T &x,const T &y)
{
    if(x<y)x=y;
}

const int N=1e3+5,U=256;
int n;
char s[N];
int pre[N],nex[N];
int a[U][N];
int dp[N];

int main()
{
    freopen("1.in","r",stdin);freopen("1.out","w",stdout);
    int tt;
    cin>>tt;
    while(tt--)
    {
        scanf("%s",s+1);
        int n=strlen(s+1);
        char mx=0;
        rep(i,1,n)chmax(mx,s[i]);

        rep(i,1,n) {nex[i]=i+1;pre[i]=i-1;}
        pre[1]=n;nex[n]=1;

        rep(i,0,mx)*a[i]=0;
        rep(i,1,n)a[s[i]][++*a[s[i]]]=i;
        rep(c,0,mx-1)
        {
            int top=0;
            rep(i,1,*a[c])
            {
                int x=a[c][i];
                if(s[pre[x]]==c) 
                {
                    nex[pre[x]]=nex[x];
                    pre[nex[x]]=pre[x];
                }
                else a[c][++top]=a[c][i];
            }
            *a[c]=top;
            rep(i,1,top) 
            {
                int x=a[c][i];
                nex[pre[x]]=nex[x];
                pre[nex[x]]=pre[x];
            }
        }

        int lastc=0;
        *a[0]=1;
        a[0][1]=0;
        nex[0]=1;
        dp[0]=0;
        rep(c,1,mx-1)
        if(*a[c])
        {
            int mn=N,cant=-1;
            rep(i,1,*a[lastc])
            {
                int k=a[lastc][i];
                int j=nex[k];
                if(s[j]==c&&s[pre[j]]!=c) 
                {
                    int now=dp[k]-1;
                    if(now<mn)
                    {
                        mn=now;
                        if(*a[c]==1) cant=-1;
                        else cant=j;
                    }
                    else 
                    if(now==mn)cant=-1;
                }
                else
                {
                    int now=dp[k];
                    if(now<mn){mn=now;cant=-1;}
                    else 
                    if(now==mn)cant=-1;
                }
            }
            mn+=*a[c];
            rep(i,1,*a[c])
            {
                int j=a[c][i];
                if(j!=cant)dp[j]=mn;
                else dp[j]=mn+1;
            }
            lastc=c;
        }

        int ans=N;
        rep(i,1,*a[lastc])chmin(ans,dp[a[lastc][i]]);
        printf("%d\n",ans);
    }
}