本解説では，操作後の文字列を \(S'\) と表記して，もとの \(S\) と区別します．

\(\ell=r\) として操作をすれば \(S'=S\) とできるため，答えが \(S\) よりも辞書順で後に現れることはないです．以降，\(\ell + 1 \leq r\) の場合を考えます．

まず，最適な \(\ell\) を決めます．\(S_{\ell} > S_{\ell+1}\) ならば，操作によって \(S\) よりも辞書順で小さい文字列を得ることができます．逆に，すべての \(1 \leq i \leq N-1\) で \(S_{i} \leq S_{i+ 1}\) ならば，どのように操作を行っても \(S\) より辞書順で小さい文字列を作ることができません．辞書順で小さくできる場合，できるだけ先頭に近い文字の辞書順を小さくしたほうが文字列全体の辞書順も小さくなるため，\(\ell\) としては \(S_i > S_{i+1}\) が成り立つ \(1 \leq i \leq N-1\) のうちもっとも小さいものを選ぶのが最適です．そのような \(i\) が存在しなければ，\(\ell=r\) として操作をするのが最適で，答えは \(S\) です．

次に，最適な \(r\) を決めます．\(S_\ell\) 以下の文字が \(S\) の \(\ell+1\) 文字目以降に続く限り，\(S_\ell\) を後ろに追いやるほうが辞書順で良いので，\(r\) は，\(S_{\ell} < S_{j+1}\) が成り立つ \(\ell+1 \leq j \leq N-1\) のうち最小のものが最適です．そのような \(j\) が存在しなければ，\(r=N\) が最適です．

時間計算量は \(O(N)\) です．

実装例 (Python)

def solve():
    N = int(input())
    S = input()
    l = -1
    for i in range(N - 1):
        if S[i] > S[i + 1]:
            l = i
            break
    if l == -1:
        print(S)
        return
    r = N
    for j in range(l + 1, N):
        if S[l] < S[j]:
            r = j
            break
    print(S[:l] + S[l + 1 : r] + S[l] + S[r:])


T = int(input())
for _ in range(T):
    solve()