In this editorial, we denote the string after the operation by \(S'\) to distinguish it from \(S\).

Picking \(\ell=r\) makes \(S'=S\), the answer is not lexicographically greater than \(S\). Now we assume \(\ell + 1 \leq r\).

First, we decide the optimal \(\ell\). If \(S_{\ell} > S_{\ell+1}\), then the operation yields a string lexicographically smaller than \(S\). Conversely, if \(S_{i} \leq S_{i+ 1}\) for all \(1 \leq i \leq N-1\), then no operation makes \(S\) lexicographically smaller. If any operation does, the earlier a character is made lexicographically smaller, the smaller the entire string becomes lexicographically, so it is optimal to set \(\ell\) to the smallest \(1 \leq i \leq N-1\) with \(S_i > S_{i+1}\). If no such \(i\) exists, picking \(\ell=r\) is optimal, and the answer is \(S\).

Next, we decide the optimal \(r\). It is better to repeatedly “defer” \(S_\ell\) as long as the next character to \(S_\ell\) is smaller than \(S_\ell\) itself. Thus, the optimal \(r\) is the smallest \(\ell+1 \leq j \leq N-1\) with \(S_{\ell} < S_{j+1}\), or \(r=N\) if no such \(j\) exists.

The time complexity is \(O(N)\).

Sample code (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()