Hints: String Cutting

Before anything clever, when can we even succeed?

Each of our $k$ (or more) parts must have length at least $l$, and the parts are disjoint and cover $s$. So we need:

If this fails, print NO.

And if $k=1$: we want the $1$st (smallest) part to be as large as possible. Any proper cut makes the smallest part strictly shorter than $s$, so we just output $s$ itself as one part.

So assume from now on:

The answer string is some part of our partition. Every part is a contiguous substring of $s$, so the answer is $s[i..j]$ for some $i \le j$. Think of the unknowns as:

• $i$: starting index in $s$ of the $k$-th sorted part,
• $j$: ending index in $s$ of the $k$-th sorted part.

All other parts live either entirely in $s[0..i-1]$ (call them left parts) or entirely in $s[j+1..n-1]$ (right parts), because parts are contiguous and don’t overlap.

So a partition looks like:

Say there are $m$ left parts and $r$ right parts. Then the total number of parts is $m+1+r \ge k$.

Because every part has length $\ge l$:

• The $m$ left parts fit inside $s[0..i-1]$, which has length $i$. So $m \cdot l \le i$, i.e. $$ m \le \left\lfloor \tfrac{i}{l} \right\rfloor. $$
• The $r$ right parts fit inside $s[j+1..n-1]$, which has length $n-1-j$. So $r \cdot l \le n - 1 - j$, i.e. $$ j \le n - 1 - r \cdot l. $$

These two inequalities are the only “size” constraints on the partition — everything else is just about where we cut.

Fix the starting index $i$. If we extend the right end $j$ by one character, the new candidate is $s[i..j]$ followed by one more character. Any extension of a string is lexicographically $\ge$ the original (strict if we extend a non-empty string by anything, because the shorter string is a proper prefix of the longer one).

So for a fixed start $i$, longer is always at least as good. We should push $j$ as far right as the constraints allow.

Question: given that the $k$-th sorted part is $s[i..j]$, how large can $j$ be?

Answer to Hint 4 / reasoning:

Outside of the candidate we have $m + r$ parts, and we need $m + r + 1 \ge k$, i.e. $m + r \ge k - 1$. We’d like to spend as much budget as possible on the candidate, which means using as few “outside” characters as possible.

• Use the maximum number of left parts: $m = \lfloor i/l \rfloor$. Then left parts exactly fill the prefix $s[0..i-1]$.
• The remaining outside parts must be right parts: $r = k - 1 - m$.
• With $r$ right parts, the candidate can end as far as $j = n - 1 - r \cdot l$.

So for any partition whose $k$-th part starts at $i$,

Call this upper bound $\mathrm{rp}(i)$. Then the $k$-th part is $s[i..j]$ with $j \le \mathrm{rp}(i)$, which is a prefix of $s[i..\mathrm{rp}(i)]$. A prefix is lex $\le$ the full string, so:

So for each possible start $i$, $s[i..\mathrm{rp}(i)]$ is an upper bound on the $k$-th part.

Valid starts $i$: either $i = 0$ (no left parts) or $i \ge l$ (need room for at least one left part of length $\ge l$).

Now the other direction: for each valid $i$, show we can achieve the $k$-th part $=$ $s[i..\mathrm{rp}(i)]$.

Answer to Hint 5 / construction:

Take the partition:

• $m = \lfloor i/l \rfloor$ left parts of length $l$ each, then (if $i$ is not a multiple of $l$) the last left part absorbs the extra characters — actually, since $m \cdot l \le i$, we can just cut the prefix into $m$ parts with one of them longer. The simplest choice: first $m-1$ left parts of length $l$, last left part of length $i - (m-1)\cdot l \ge l$.
• The candidate $s[i..\mathrm{rp}(i)]$.
• $r = k - 1 - m$ right parts of length $l$ each (which exactly fills $s[\mathrm{rp}(i)+1..n-1]$).

This gives exactly $k$ parts, each of length $\ge l$. After sorting, the $k$-th (i.e. the largest) is at least $s[i..\mathrm{rp}(i)]$ — because the candidate itself is one of our $k$ parts, so the max is $\ge$ candidate.

Combined with the upper bound from Hint 5: for each $i$, the best achievable $k$-th part is at least the candidate, but also any $k$-th part starting at $i$ is at most the candidate. So the answer is:

where $\max$ is lexicographic.

Valid starts:

• $i = 0$ (initial candidate: $\mathrm{rp}(0) = n - 1 - (k-1)l$).
• $i \in [l, n-l]$ (need at least one left part, and the candidate must have length $\ge l$).

For each $i$, compute:

Skip $i$ if $\mathrm{rp}(i) - i + 1 < l$ (candidate too short).

Keep the lex-max candidate seen so far. The answer is that max.

Lex-compare two substrings $s[a..b]$ and $s[c..d]$ the naive way: scan character by character up to $\min(b-a, d-c)$ and break on first mismatch; if neither side broke, the longer one is larger.

Each comparison is $O(n)$, and there are $O(n)$ values of $i$, so total $O(n^2)$. That’s comfortably within budget for $n \le $ a few thousand, and is fine pedagogically for any $n$ if we’re just learning the idea.

Answer to Hint 7 / edge detail:

For $i \in [1, l-1]$: the prefix $s[0..i-1]$ has length $< l$, so it cannot be any number of parts of length $\ge l$ — not even one. So such an $i$ cannot be the start of the $k$-th part. That’s why the iteration in the classic writeup jumps from $i=0$ straight to $i=l$.

For $i = 0$: no left parts at all, $m=0$, $r=k-1$, candidate ends at $n-1-(k-1)l$. This is your very first candidate.

Answer to Hint 8 / overflow handling:

If $i$ is huge, $m = \lfloor i/l \rfloor$ can be $\ge k$. Then $r = k - 1 - m < 0$, which doesn’t make sense as “number of right parts”.

Interpretation: we have more than enough room on the left for $k-1$ parts, so we can place zero right parts and let the candidate extend all the way to $n - 1$. In code: clamp $r$ to $0$, i.e.\ $\mathrm{rp}(i) = n - 1$.

(You can also think of the extra “virtual” right parts as being absorbed into more left parts; either way the candidate is $s[i..n-1]$.)

Answer to Hint 9 / pseudocode:

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

cl, cr = 0, n - 1 - (k-1) * l

for i = l to 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[cl..cr]:
        cl, cr = i, rp

print "YES"
print s[cl..cr]

This is the full $O(n^2)$ algorithm.

$n=11, l=2, k=5$, $s=\text{abracadabra}$. Feasible since $2\cdot 5 = 10 \le 11$.

Initial: $\mathrm{rp}(0) = 11 - 1 - 4\cdot 2 = 2$, candidate $s[0..2] = \text{abr}$.

Sweep $i = 2 \ldots 9$ (compute $m$, $r$, $\mathrm{rp}$, candidate):

• $i=2$: $m=1,\,r=3,\,\mathrm{rp}=4 \Rightarrow$ candidate $\text{rac}$. $\text{rac} > \text{abr}$, update.
• $i=3$: candidate $\text{ac}$, $< \text{rac}$.
• $i=4$: $m=2,r=2,\mathrm{rp}=6\Rightarrow \text{cad}$, $<\text{rac}$.
• $i=5$: $\text{ad}$, $<\text{rac}$.
• $i=6$: $m=3,r=1,\mathrm{rp}=8\Rightarrow \text{dab}$, $<\text{rac}$.
• $i=7$: $\text{ab}$, $<\text{rac}$.
• $i=8$: $m=4,r=0,\mathrm{rp}=10\Rightarrow \text{bra}$, $<\text{rac}$.
• $i=9$: $\text{ra}$, $<\text{rac}$ (prefix).

Answer: $\text{rac}$, matching the sample.

The $O(n^2)$ algorithm is correct but has $n$ starts and each comparison can scan up to $n$ characters.

A suffix array plus LCP array plus a sparse table for range-min over LCPs gives $O(1)$ lexicographic comparison of any two substrings after $O(n \log n)$ preprocessing. Plugging that into the loop turns the whole thing into $O(n \log n)$ per test case, which is what the model solution does.

You don’t need to know suffix arrays and LCPs to understand this problem — the $O(n^2)$ version already contains all of the combinatorial ideas. Learning SA+LCP later is only about speeding up the string comparison at the end.