Editorial: String Cutting

Given a string $s$ of length $n$ and integers $l, k$, cut $s$ into $k$ or more contiguous parts, each of length at least $l$. Sort the parts lexicographically and look at the $k$-th smallest. Maximize it.

• If $l \cdot k > n$, we cannot even fit $k$ parts of length $\ge l$: output NO.
• If $k = 1$, the $1$st smallest is the smallest part. Making more cuts can only produce something lex $\le s$ (a strict prefix of $s$ is smaller than $s$). So the best is to keep $s$ as a single part. Output $s$.

Assume from now on $l \cdot k \le n$ and $k \ge 2$.

Every part is a contiguous substring of $s$, so the $k$-th sorted part is $s[i..j]$ for some $0 \le i \le j \le n-1$.

In any partition where $s[i..j]$ is a part, every other part lies entirely in $s[0..i-1]$ (a left part) or entirely in $s[j+1..n-1]$ (a right part). Let there be $m$ left parts and $r$ right parts. Total parts $= m + 1 + r \ge k$.

Since every part has length $\ge l$:

Fix the starting index $i$ of the candidate and look at its end $j$. If we push $j$ one character to the right, the new candidate is the old one with one more character appended. Lexicographically, extending a non-empty string strictly increases it (the shorter string becomes a proper prefix of the longer one), and in any case never decreases it.

So, for fixed $i$, the candidate wants $j$ to be as large as possible.

To push $j$ as far as possible we should put the minimum required “other” parts outside. We need $m + r \ge k - 1$, so use $m = \lfloor i/l \rfloor$ (the max allowed on the left) and $r = k - 1 - m$ (the remaining, must go on the right). Then

If $m \ge k-1$ (i.e. the prefix alone already has room for $k-1$ length-$l$ parts), clamp $r$ to $0$ and $\mathrm{rp}(i) = n-1$.

For any partition whose $k$-th part starts at $i$:

• its end $j$ satisfies $j \le \mathrm{rp}(i)$,
• so the part $s[i..j]$ is a (possibly proper) prefix of $s[i..\mathrm{rp}(i)]$,
• so it is lex $\le s[i..\mathrm{rp}(i)]$.

Valid starts $i$:

• $i = 0$ (no left parts, $m = 0$, $\mathrm{rp}(0) = n - 1 - (k-1)\cdot l$).
• $i \in [l, n-l]$ (need at least one length-$\ge l$ left part, and candidate itself must have length $\ge l$).
• $i \in [1, l-1]$ is impossible: the prefix would be too short to contain any left part of length $\ge l$.

For each valid $i$, build this explicit partition with exactly $k$ parts, each of length $\ge l$:

• $m = \lfloor i/l \rfloor$ left parts filling $s[0..i-1]$ — e.g. the first $m-1$ of length $l$ and the last one of length $i - (m-1)\cdot l \ge l$.
• The candidate $s[i..\mathrm{rp}(i)]$, of length $\ge l$.
• $r = k - 1 - m$ right parts of length exactly $l$, filling $s[\mathrm{rp}(i)+1..n-1]$.

After sorting these $k$ parts, the largest one is the $k$-th (since there are exactly $k$ parts). The candidate is one of them, so the $k$-th $\ge$ candidate.

Combining both directions: for each valid $i$, the best achievable value of the $k$-th part, maximized over partitions whose $k$-th part starts at $i$, is exactly

Therefore the global answer is

under lex order.

if l * k > n:              print "NO"; return
if k == 1:                 print "YES"; print s; return

best_l, best_r = 0, n - 1 - (k-1) * l      # i = 0

for i = l, l+1, ..., n-l:
    m  = i / l
    r  = max(k - 1 - m, 0)
    rp = min(n - 1 - r * l, n - 1)
    if rp - i + 1 < l: continue

    if s[i..rp]  >_lex  s[best_l..best_r]:
        best_l, best_r = i, rp

print "YES"
print s[best_l..best_r]

Each iteration performs a lexicographic comparison of two substrings of $s$ in $O(n)$ time (scan until mismatch; shorter prefix loses on ties). With up to $n$ iterations, the total is $O(n^2)$.

For the full constraints ($n$ up to $10^6$ with $\sum n \le 10^6$), this is too slow in the worst case, but:

• Under the “sum of $n$” constraint, single large tests are the hard ones, and $O(n^2)$ with $n \le$ a few thousand is fine.
• The algorithm is fully correct; the only thing that needs speeding up for the full constraint is the substring comparison step.

Build a suffix array of $s$ together with its LCP array, and preprocess the LCP array with a sparse table for range minimum queries. Then lex-comparison of two substrings $s[a..b]$ and $s[c..d]$ takes $O(1)$:

1. Look up ranks of positions $a$ and $c$ in the suffix array.
2. Range-min on the LCP array between those ranks gives the length of the common prefix of the two suffixes starting at $a$ and $c$.
3. Combine that common-prefix length with the two substring lengths to decide the order.

Plugging this into the loop replaces the $O(n)$ comparison with $O(1)$, giving $O(n \log n)$ overall (dominated by suffix array construction). This is exactly what the model solution does. You don’t need any of this to understand why the algorithm works — the combinatorial core is the $O(n^2)$ version above.