Proposed Solution

Task. Given a string $s$ of length $n$ over $\{\texttt{a},\dots,\texttt{z}\}$, find the minimum number of positions to change so that $s$ becomes a Lyndon string. Constraints: $n \le 3000$, $\sum n^2 \le 9\cdot 10^6$.

Conventions. Letters are numbered $\texttt{a}=0,\dots,\texttt{z}=25$, and we write $Z=25$. A string $t$ is Lyndon if $t<t[i..]$ for every proper suffix $t[i..]$ with $1\le i<n$. We want $$\mathrm{OPT}=\min_{t\ \text{Lyndon},\ |t|=n} d_H(s,t),$$ where $d_H$ is the Hamming distance. For $n=1$ the answer is $0$, so from now on $n\ge 2$.

A note on the samples. As printed, samples 2 and 3 contradict the standard definition: abac is already Lyndon (answer $0$), and aaaa needs only one change (aaab). The explanations in the statement match the inputs aaaaa $\to 1$ (aaaab) and bbaa $\to 2$ (abac). We solve the standard problem.

What is proved and what is not. Lemmas 1–5 below are proved: they show that every number the program can output is the distance to a real Lyndon word, so the output is never smaller than $\mathrm{OPT}$, and that the pruning is safe. The opposite inequality (the output is not larger than $\mathrm{OPT}$) rests on three structural claims C1–C3 in Section 3, which we only verified by exhaustive search. We also have no proven worst-case bound for the running time of the DP phase, only measurements. We say this up front so that nobody mistakes the empirical parts for theorems.

1. Lyndon words via a pointer

Build $t$ from left to right and maintain a period $p$. Set $p_1=1$ and for $i=1,\dots,n-1$ let $r_i=i-p_i$ and compare $t[i]$ with the reference letter $t[r_i]$: $$\begin{cases} t[i]<t[r_i] & \text{forbidden},\\ t[i]=t[r_i] & \text{copy step: } p_{i+1}=p_i,\\ t[i]>t[r_i] & \text{B step: } p_{i+1}=i+1 . \end{cases}$$ Equivalently, a pointer $r$ starts at $0$; a copy step does $r\leftarrow r+1$, and a B step does $r\leftarrow 0$.

We use the classical fact behind Duval's algorithm (Duval, 1983). Let $w$ be a Lyndon word, $k\ge 1$, $u$ a proper prefix of $w$ (possibly empty), $x=w^k u$, let $d=w[|u|]$ be the letter that follows $u$ in $w$, and let $c$ be a letter. Then (i) if $c<d$, the word $xc$ is not a prefix of any Lyndon word; (ii) if $c=d$, then $xc=w^k(uc)$ has the same form; (iii) if $c>d$, then $xc$ is Lyndon.

Lemma 1. $t$ is Lyndon if and only if the process never meets a forbidden step and $p_n=n$.

Proof. Induct on $i$ with the invariant: if no forbidden step occurred so far, then $t[0..i)=w^k u$ where $w=t[0..p_i)$ is Lyndon, $k\ge1$ and $|u|<p_i$. Since $t[0..i)$ has period $p_i$, we have $t[i-p_i]=w[|u|]=d$, that is, $t[r_i]=d$. Now apply the classical fact to the next letter $c=t[i]$. A forbidden step means $t[0..i]$ is not a prefix of any Lyndon word, so $t$ is not Lyndon. A copy step keeps the form. A B step makes $t[0..i]$ itself Lyndon, hence $p_{i+1}=i+1$. At the end, if $p_n=n$ then $t$ is Lyndon. If $p_n<n$ then $t=w^k u$ with $k\ge 2$ or $u\ne\varepsilon$; then $t$ has a proper suffix that is also a prefix of $t$ (a border), and a proper prefix of a word is smaller than the word, so $t$ is not smaller than all its proper suffixes. $\square$

Corollary 1 (block form). Every Lyndon word of length $n\ge 2$ is $t[0]$ followed by blocks. A block starting at position $y$ has the form $$t[0..e)\cdot c,\qquad c>t[e],\quad e\ge 0,$$ that is, $e$ copy steps $t[y+i]=t[i]$ followed by one B step at position $y+e$. The last step is always a B step. In particular all letters of $t$ are $\ge t[0]$, and $t$ is determined by its sequence of pairs $(e_j,c_j)$.

2. The first character

Lemma 2. If $t$ is Lyndon ($n\ge2$) and $y<t[0]$, then the word $t'$ obtained by replacing $t[0]$ with $y$ is Lyndon.

Proof. By Corollary 1 all other letters of $t$ are $\ge t[0]>y$. So $t'[0]$ is strictly smaller than the first letter of every proper suffix, hence $t'$ is smaller than every proper suffix. $\square$

Corollary 2. There is an optimal $t$ with $t[0]=m\in\{s[0],\texttt{a}\}$ and $m<Z$.

Proof. Take an optimal $t^{\ast}$. If $t^{\ast}[0]>s[0]$, lower it to $s[0]$: the word is still Lyndon by Lemma 2 and the distance does not increase. If $t^{\ast}[0]<s[0]$, lower it to $\texttt{a}$: still Lyndon, and the position was already a mismatch, so the distance is unchanged. Finally $m=Z$ is impossible, because then all letters would be $\ge Z$, so $t=\texttt{z}^n$, which is not Lyndon for $n\ge 2$. $\square$

3. Candidates $(m,a)$ and the structural claims

Fix $m$ and let $a\ge 1$ be the length of the leading run, i.e. $t=m^a\cdots$ with $t[a]>m$ being the first B step ($a\le n-1$). The cost of the first $a$ positions is exactly $$\mathrm{lead}(m,a)=[m\ne s[0]]+\#\{x\in[1,a): s[x]\ne m\},$$ which is non-decreasing in $a$. This leaves at most $2n$ candidate pairs $(m,a)$.

Structural claims (verified, not proved). There is an optimal $t$ such that, for its pair $(m,a)$:

• C1. Every position $x\ge a$ with $t[x]\ne s[x]$ is one of two kinds: a raise, which is a B step with $t[x]=t[r]+1$ (it costs $1$ when $s[x]\le t[r]<Z$), or a mismatching copy, which is a copy step $t[x]=t[r]$ with $s[x]<t[r]$.
• C2. When computing the cheapest way to reach each prefix length $y$ (the length of the current Lyndon prefix), it suffices to keep a single content of $t[0..y)$ per $y$, the cheapest one.
• C3. From a state $y$ it suffices to consider the block ends listed in Section 5.

These were found and checked by brute force (Section 7). An earlier version of C1 without the "mismatching copy" option was wrong. For the $n=97$ string aaaaaaabaaaaaaadaaaaaaabaaabaaaaaaabaaaaaaaaaaaaaaacaaaaaaabaaaaaaadaaaaaaabaaabaaaaaaabaaaaaaada the optimum is $2$: change position $43$ to d (a mismatching copy of $t[15]=\texttt{d}$, which makes the two halves of the string equal) and change the last letter to b. The old model only reached $3$.

4. Greedy upper bound for a fixed $(m,a)$

Set $t[0..a)=m^a$ and $p=1$, and scan $x=a,a+1,\dots,n-1$ with $\mathit{ref}=t[x-p]$:

• if $s[x]>\mathit{ref}$: put $t[x]=s[x]$ and $p\leftarrow x+1$ (a free B step);
• if $s[x]=\mathit{ref}$: put $t[x]=s[x]$ (a free copy);
• if $s[x]<\mathit{ref}$: pay $1$. If $\mathit{ref}<Z$, put $t[x]=\mathit{ref}+1$ and $p\leftarrow x+1$ (a raise). Otherwise put $t[x]=\mathit{ref}$, a copy, because we cannot go above $\texttt{z}$.

If at the end $p\ne n$ (the last step was a copy), pay $1$ more and raise the last letter to $\mathit{ref}+1$. This needs $\mathit{ref}<Z$; otherwise the candidate is discarded.

Lemma 3 (soundness). Every candidate produced by this greedy is a Lyndon word, and the cost it reports equals its Hamming distance to $s$.

Proof. Every step satisfies $t[x]\ge t[x-p]$, so no forbidden step occurs, and after the final fix $p_n=n$; apply Lemma 1. As for the cost: the first $a$ positions contribute $\mathrm{lead}(m,a)$; a free step has $t[x]=s[x]$; a paid raise or copy has $t[x]\ne s[x]$ because $t[x]\in\{\mathit{ref},\mathit{ref}+1\}$ while $s[x]<\mathit{ref}$; and the final raise changes a letter that was equal to $s[n-1]$. $\square$

When the alphabet is unbounded above and $\texttt{z}$ never interferes, this greedy is exact (observed by exhaustive search, not proved). It takes $O(n)$ per pair, so $O(n^2)$ in total. Its role in the final program is to provide a strong upper bound.

5. Exact DP for a fixed $(m,a)$

The greedy is not enough in two situations: the top letter $\texttt{z}$ cannot be raised, and sometimes a mismatching copy beats a raise (the $n=97$ example). So for each surviving pair $(m,a)$ we run a DP over $y\in[a+1,n]$, where state $y$ means that $t[0..y)$ is a Lyndon prefix (the step before $y$ was a B step). For every $y$ we keep the cheapest cost and its content. The content is stored as the base string $\tilde s=m^a\,s[a..n)$ together with a short sorted list of overrides, the positions where $t\ne\tilde s$.

Initial state. Position $a$ is the first B step, with reference $m$. If $s[a]>m$ we go to $y=a+1$ at cost $\mathrm{lead}$. Otherwise, if $m<Z$, we go to $y=a+1$ at cost $\mathrm{lead}+1$ with the override $(a,m+1)$.

Transitions from a state $y$. Scan $e=0,1,2,\dots$ with $x=y+e$ and $\mathit{ref}=t[e]$. (Positions $\ge y$ are read as $t[p-y]$, because a block copies the prefix.) Let $\mathit{ham}$ be the number of mismatching copies made so far in this block.

• If $s[x]>\mathit{ref}$: this is a free end. Go to state $x+1$ at cost $+\mathit{ham}$ and stop.
• If $s[x]=\mathit{ref}$: continue. If $\mathit{ref}<Z$, remember this position as the last equality.
• If $s[x]<\mathit{ref}<Z$: option (A) end the block here with $t[x]=\mathit{ref}+1$, going to state $x+1$ at cost $+\mathit{ham}+1$; option (B) copy $\mathit{ref}$ at cost $+1$ and continue scanning.
• If $s[x]<\mathit{ref}=Z$: copy $Z$ at cost $+1$ and continue; in addition, raise the last equality $e'$ (set $t[y+e']=t[e']+1$ and go to state $y+e'+1$ at cost $+\mathit{ham}_{e'}+1$, where $\mathit{ham}_{e'}$ is the value of $\mathit{ham}$ at that moment).
• If the end of the string is reached without ending the block: raise the last equality in the same way.

The answer for the pair is the cost of state $n$.

Lemma 4 (soundness). Every state $y$ corresponds to a real Lyndon word of length $y$ whose Hamming distance to $s[0..y)$ equals the stored cost. Hence the cost of state $n$ is the distance to a real Lyndon word, and it is $\ge \mathrm{OPT}$.

Proof. Induct on $y$. The initial state is the word $m^a c$ with $c>m$, a block with $e=a-1$. Each transition appends a block "copy of the prefix $t[0..e)$, then a letter $c>t[e]$", where the copy steps are equalities by construction and the final letter is either $s[x]>\mathit{ref}$ or $\mathit{ref}+1$; by Lemma 1 the result is Lyndon. The added cost is the number of appended positions that differ from $s$: mismatching copies are counted in $\mathit{ham}$, a raised end letter costs $1$ because $s[x]\le\mathit{ref}<\mathit{ref}+1$, and a free end has $t[x]=s[x]$. The override list records exactly the positions where $t\ne\tilde s$. $\square$

Together with Lemma 3 and Corollary 2, this shows that the output of the program is always $\ge\mathrm{OPT}$. That it is also $\le\mathrm{OPT}$ is exactly the content of claims C1–C3.

6. Pruning and complexity

Initial upper bound. The word $\texttt{a}\cdot\bigl(s[1..]\text{ with every }\texttt{a}\text{ replaced by }\texttt{b}\bigr)$ is Lyndon (its first letter is the unique smallest) and costs $[s[0]\ne\texttt{a}]+\#\{i\ge1: s[i]=\texttt{a}\}$. We start from this value and take the minimum with all greedy candidates of Section 4.

Lemma 5 (safe pruning). (i) Pairs with $\mathrm{lead}(m,a)\ge\mathrm{best}$ can be skipped, and because $\mathrm{lead}$ is non-decreasing in $a$, the loop over $a$ can stop there. (ii) States whose cost is $\ge\mathrm{best}$ can be dropped.

Proof. All costs are sums of non-negative terms, so a partial cost is a lower bound on the final cost of any completion, and a completion of cost $\ge\mathrm{best}$ cannot improve the answer. $\square$

Complexity. The greedy phase is $O(n)$ per pair, and there are at most $2n$ pairs, so it costs $O(n^2)$ time, which matches $\sum n^2\le 9\cdot10^6$. For the DP phase we have no worst-case bound better than the naive polynomial one (each state may scan up to $n$ letters), but with the upper bound above and Lemma 5, almost every pair is pruned immediately. Measured: for $n=3000$ and dozens of input families (all a, all z, random over small alphabets, periodic with noise, z-heavy, $\texttt{z}^{n/2}\texttt{a}^{n/2}$, and so on) the program finishes in at most $0.25$ s, and $10^4$ tests with $n=30$ take about $0.04$ s.

7. Validation performed (for C1–C3)

• Exhaustive over all Lyndon words (minimum Hamming distance), for alphabets of size $K=2,\dots,8$ (with $Z=K-1$ in the code) and $n$ up to $14$: several hundred thousand strings, including strings concentrated on the top letter. No mismatch.
• Exhaustive over all sets of at most $R$ modifications ($R=2,3$) for $n$ up to $130$ with $K=3,\dots,6$, and also for $K=26$ with strings over $\{\texttt{a},\texttt{b},\texttt{c},\texttt{d},\texttt{y},\texttt{z}\}$. The strings were structured (periodic with mutations, "$Q$ + separator + $Q$", mostly a, perturbed Lyndon words): about $3.7\cdot10^5$ strings, no mismatch. Whenever the enumeration found nothing within radius $R$, the program also returned a value larger than $R$.
• Since the code is parametric in $Z$, small alphabets exercise the "cannot raise above the top letter" logic of Sections 4–5, which only matters for strings containing y or z.

This is strong evidence, but it is not a proof of C1–C3.

8. Code

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int Z = 25;
const int INF = 1e9;
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        static char buf[3105];
        scanf("%d %s", &n, buf);
        vector<int> s(n);
        for (int i = 0; i < n; i++) s[i] = buf[i] - 'a';
        if (n == 1) {
            puts("0");
            continue;
        }
        int best = (s[0] != 0);
        for (int i = 1; i < n; i++) best += s[i] == 0;
        vector<int> ms = {s[0]};
        if (s[0] != 0) ms.push_back(0);
        vector<int> tg(n);
        for (int m : ms) {
            if (m == Z) continue;
            int ld = (m != s[0]);
            for (int a = 1; a < n; a++) {
                if (a >= 2) ld += (s[a - 1] != m);
                if (ld >= best) break;
                int cost = ld, per = 1, lastRef = 0;
                for (int x = 0; x < a; x++) tg[x] = m;
                for (int x = a; x < n && cost < best; x++) {
                    int ref = tg[x - per];
                    lastRef = ref;
                    if (s[x] > ref) {
                        tg[x] = s[x];
                        per = x + 1;
                    } else if (s[x] == ref) tg[x] = s[x];
                    else {
                        cost++;
                        if (ref < Z) {
                            tg[x] = ref + 1;
                            per = x + 1;
                        } else tg[x] = ref;
                    }
                }
                if (cost >= best) continue;
                if (per != n) {
                    if (lastRef >= Z) continue;
                    cost++;
                }
                best = min(best, cost);
            }
        }
        vector<int> sp(n), dp(n + 1);
        vector<vector<pii>> ov(n + 1);
        for (int m : ms) {
            if (m == Z) continue;
            int lead = (m != s[0]);
            for (int a = 1; a < n; a++) {
                if (a >= 2) lead += (s[a - 1] != m);
                if (lead >= best) break;
                for (int x = 0; x < n; x++) sp[x] = x < a ? m : s[x];
                fill(dp.begin(), dp.end(), INF);
                for (int y = 0; y <= n; y++) ov[y].clear();
                auto add = [&](int y, int cost, const vector<pii>& base, const vector<pii>& extra) {
                    if (cost < dp[y] && cost < best) {
                        dp[y] = cost;
                        ov[y] = base;
                        ov[y].insert(ov[y].end(), extra.begin(), extra.end());
                    }
                };
                vector<pii> none;
                if (s[a] > m) add(a + 1, lead, none, none);
                else if (m < Z) add(a + 1, lead + 1, none, vector<pii>{{a, m + 1}});
                for (int y = a + 1; y < n; y++) {
                    if (dp[y] >= best) continue;
                    const vector<pii>& O = ov[y];
                    auto tget = [&](int p) {
                        while (p >= y) p -= y;
                        auto it = lower_bound(O.begin(), O.end(), pii(p, -1));
                        if (it != O.end() && it->first == p) return it->second;
                        return sp[p];
                    };
                    int ham = 0, lastEq = -1, lastEqHam = 0, lastEqZc = 0, lastEqVal = 0;
                    bool ended = false;
                    vector<pii> zc;
                    for (int e = 0; y + e <= n - 1; e++) {
                        int ref = tget(e), x = y + e, v = s[x];
                        if (v > ref) {
                            add(x + 1, dp[y] + ham, O, zc);
                            ended = true;
                            break;
                        }
                        if (v == ref) {
                            if (ref < Z) {
                                lastEq = e;
                                lastEqHam = ham;
                                lastEqZc = zc.size();
                                lastEqVal = ref;
                            }
                        } else if (ref < Z) {
                            vector<pii> ex = zc;
                            ex.push_back({x, ref + 1});
                            add(x + 1, dp[y] + ham + 1, O, ex);
                            ham++;
                            zc.push_back({x, ref});
                            if (dp[y] + ham >= best) break;
                        } else {
                            if (lastEq >= 0) {
                                vector<pii> ex(zc.begin(), zc.begin() + lastEqZc);
                                ex.push_back({y + lastEq, lastEqVal + 1});
                                add(y + lastEq + 1, dp[y] + lastEqHam + 1, O, ex);
                            }
                            ham++;
                            zc.push_back({x, Z});
                        }
                    }
                    if (!ended && lastEq >= 0) {
                        vector<pii> ex(zc.begin(), zc.begin() + lastEqZc);
                        ex.push_back({y + lastEq, lastEqVal + 1});
                        add(y + lastEq + 1, dp[y] + lastEqHam + 1, O, ex);
                    }
                }
                if (dp[n] < best) best = dp[n];
            }
        }
        printf("%d\n", best);
    }
}