首先如果 $s$ 不是 Lyndon 直接有解，如果 $s_1$ 小于 $s_{2 \sim n}$ 的所有字符就无解。然后此时 $s_1$ 一定是 $s$ 中最小字符。

令 $c = s_1$。考虑 $c$ 在 $s$ 中第二次出现位置 $l$ 和最后一次出现位置 $r$。如果 $[l, r]$ 中有非 $c$ 字符，此时 $s$ 形如 $c A c^k x B c C$（其中 $A, B, C$ 为可空字符串，$x$ 为非 $c$ 字符，$k \ge 1$），可以把 $s$ 切成 $c A c^k \mid x B c C$，显然两段都是非 Lyndon。

否则若 $l = 2$，此时 $s$ 形如 $c^k A$（其中 $A$ 为可空字符串，$k \ge 2$），并且 $A$ 的最小字符 $> c$。那么我们可以把前面纯 $c$ 段合并，切成 $c^k \mid A$，然后令 $s = A$ 递归进子问题。

否则此时 $s$ 形如 $cAcB$（其中 $A, B$ 均为不含 $c$ 的非空字符串），因为 $s$ 是 Lyndon，所以 $cAcB < cB$。设 $t = \operatorname{lcp}(cAcB, cB)$，$p$ 为第二个 $c$ 的位置。那么因为第一段必须有 border，所以第一段的结尾只能在 $[p, p + t - 1]$ 之间。

枚举 $i \in [p, p + t - 1]$。设 $f_i$ 为 $s_{i \sim n}$ 的最小字符。如果 $f_{i + 1} < s_{i + 1}$，那么 $s_{i + 1 \sim n}$ 不是 Lyndon，可以直接切成 $[1, i], [i + 1, n]$。

如果所有 $i \in [p, p + t - 1]$ 都满足 $f_{i + 1} = s_{i + 1}$，设 $q$ 为最小的下标满足 $s_q = s_{q + 1} = \cdots = s_{p + t}$，那么第一段切成 $[1, q - 1]$，然后剩余的 $s_{q \sim n}$ 递归进子问题（不切成 $[1, p + t - 1]$ 是为了防止出现首字符是唯一最小字符而无解的情况）。可以证明任意一个合法的划分方案都可以把 $q - 1$ 之前分出来的段逐步并入第一段。

由于每次递归进子问题时，$s$ 的首字符会严格变大，所以递归次数最多 $|\Sigma|$ 次，时间复杂度 $O(|\Sigma| n)$。