Nasser's Sorted Substring (Editorial)

Solution

General Idea: We need the longest non-decreasing substring we can get after changing at most one character.

Let $pre[i]$ be the length of the longest sorted substring that ends at position $i$, and let suff[i] be the length of the longest sorted substring that starts at position $i$. Both arrays can be computed in one linear pass each.

If we do not change anything, the answer is the maximum value in $pre$.

Now suppose we change the character at position $i$ to some letter. There are three useful cases:

Extend the left part: change $s[i]$ to s[i-1]. The sorted substring ending at i-1 grows by one character, so we get pre[i-1] + 1.

Extend the right part: change $s[i]$ to s[i+1]. The sorted substring starting at i+1 grows by one character on its left, so we get suff[i+1] + 1.

Merge both parts: the sorted substring ending at i-1 and the one starting at i+1 can be joined through position $i$ if s[i-1] \le s[i+1]. We then change $s[i]$ to any letter between them, for example s[i-1], and the result is pre[i-1] + suff[i+1] + 1.

The answer is the maximum over all positions $i$ and all the cases above. For n = 1 the answer is $1$.

The solution runs in $\mathcal{O}(n)$ time per test case.

#include <bits/stdc++.h>
using namespace std;
void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> pre(n), suff(n);
    int cnt = 1, ans = 1;
    for (int i = 0; i < n; i++) {
        if (i) {
            if (s[i] >= s[i - 1]) cnt++;
            else cnt = 1;
        }
        pre[i] = cnt;
        ans = max(ans, cnt);
    }
    cnt = 1;
    for (int i = n - 1; i >= 0; i--) {
        if (i != n - 1) {
            if (s[i] <= s[i + 1]) cnt++;
            else cnt = 1;
        }
        suff[i] = cnt;
        ans = max(ans, cnt);
    }
    for (int i = 0; i < n; i++) {
        if (i < n - 1) ans = max(ans, suff[i + 1] + 1);
        if (i) ans = max(ans, pre[i - 1] + 1);
        if (i > 0 && i < n - 1) {
            if (s[i + 1] >= s[i - 1])
                ans = max(ans, pre[i - 1] + suff[i + 1] + 1);
        }
    }
    cout << ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
        cout << '\n';
    }
    return 0;
}