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$: careful — we’re maximizing the $1$st sorted part, i.e. the smallest part, not the largest.

Claim: when $k=1$, the optimal is to make no cuts and output $s$ as a single part.

Proof. Let any partition (in the original left-to-right order) be $p_1, p_2, \ldots, p_K$ with $K \ge 1$. The first part $p_1$ is a prefix of $s$:

• If $K = 1$, then $p_1 = s$ and the smallest part is $s$ itself.
• If $K \ge 2$, then $p_1$ is a proper prefix of $s$ (strictly shorter), so $p_1 < s$ lexicographically. The smallest part is $\min(p_1, \ldots, p_K) \le p_1 < s$.

So any partition with more than one part has smallest $< s$, and the one-part partition achieves smallest $= s$. Hence “no cuts” is optimal for $k=1$.

Concrete example: $s = \text{abra}$, $k=1$.

• No cut: sorted parts $=[\text{abra}]$, $1$st $= \text{abra}$.
• Cut $\text{ab}\,|\,\text{ra}$: sorted $=[\text{ab},\text{ra}]$, $1$st $= \text{ab} < \text{abra}$.

(Note: $\text{ra}$ is the $2$nd (largest) here, not the $1$st — and with $k=1$ we don’t care about the largest.)

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 must cover $s[0..i-1]$ and each has length $\ge l$. So $m \cdot l \le i$. In particular:
  • $i = 0 \Rightarrow m = 0$.
  • $i \in [1, l-1] \Rightarrow$ impossible (prefix too short for even a single length-$\ge l$ part).
  • $i \ge l \Rightarrow m \in [1, \lfloor i/l \rfloor]$ is achievable.
• Symmetrically, the $r$ right parts cover $s[j+1..n-1]$ (length $n-1-j$) with each of length $\ge l$:
  • $j = n-1 \Rightarrow r = 0$.
  • $n-1-j \in [1, l-1] \Rightarrow$ impossible.
  • $n-1-j \ge l \Rightarrow r \in [1, \lfloor (n-1-j)/l \rfloor]$ is achievable.

These are the only size constraints — everything else is just about where we cut.

What if we just try every substring $s[i..j]$ of length $\ge l$ as a candidate answer?

For each $(i, j)$ we’d like to decide: is there a valid partition in which $s[i..j]$ is a part? If yes, call $(i, j)$ feasible. Then report the lex-max feasible $s[i..j]$.

Try to derive the feasibility condition from Hint 3 alone — you only need a count of parts.

Answer to Hint 4:

$(i, j)$ is feasible iff all of the following hold:

1. $j - i + 1 \ge l$ (candidate itself is long enough);
2. $i = 0$ or $i \ge l$ (the prefix is partitionable);
3. $n-1-j = 0$ or $n-1-j \ge l$ (the suffix is partitionable);
4. $\left\lfloor \tfrac{i}{l} \right\rfloor + \left\lfloor \tfrac{n-1-j}{l} \right\rfloor \;\ge\; k-1$ (the prefix and suffix can together hold at least $k-1$ length-$\ge l$ parts besides the candidate).

Claim. The answer equals the lex-max $s[i..j]$ over all feasible $(i, j)$.

Why answer $\le$ max feasible. Take any partition whose $k$-th sorted part is $P = s[i^*..j^*]$. It has $m$ left + $r$ right parts outside the candidate with $m + r \ge k-1$, $m \le \lfloor i^*/l\rfloor$, $r \le \lfloor (n-1-j^*)/l\rfloor$. So $\lfloor i^*/l\rfloor + \lfloor (n-1-j^*)/l\rfloor \ge k-1$, i.e. $(i^*, j^*)$ is feasible. Hence $P \le \max\text{-feasible}$.

Why answer $\ge$ max feasible. Take the lex-max feasible $(i^*, j^*)$. Construct a partition explicitly: cut $s[0..i^*-1]$ into $m = \lfloor i^*/l\rfloor$ parts of length $\ge l$, include $s[i^*..j^*]$ as is, cut $s[j^*+1..n-1]$ into $r' = \lfloor (n-1-j^*)/l\rfloor$ parts of length $\ge l$. Total parts $\ge k$, each $\ge l$. So this is valid. The $k$-th sorted is $\ge$ smallest of the parts, but more importantly, the candidate $s[i^*..j^*]$ is one of the parts, so the $k$-th sorted of the whole sorted list is at least as large as the candidate when the candidate is ranked $\le k$; and when the candidate is ranked $> k$, the $k$-th sorted is some other part which is $\ge$ candidate. Either way, the $k$-th sorted $\ge s[i^*..j^*]$. So the answer $\ge$ max feasible.

(For the last step in the “$\ge$” direction, a cleaner way: you can always add or redistribute length-$l$ splits so that the candidate ends up at (or beyond) the $k$-th position in sorted order; details aren’t essential — what matters is that some partition achieves the $k$-th $\ge$ candidate, which suffices.)

From Hint 5 we get a very direct algorithm:

best = ""                       # tracked as a substring (l, r) of s
for i in 0..n-1:
    for j in i+l-1 .. n-1:
        # feasibility
        pre, suf = i, n-1-j
        if pre not in {0} and pre < l: continue
        if suf not in {0} and suf < l: continue
        if (pre // l) + (suf // l) < k - 1: continue
        # update best
        if s[i..j] >_lex best: best = s[i..j]
print best

• Two nested loops over $(i, j)$: $O(n^2)$ pairs.
• Each lex comparison of two substrings is $O(n)$ (scan until mismatch; if one is a prefix of the other, the shorter is smaller).
• Total: $O(n^3)$ per test case.

This is already enough to solve the problem when $n$ is small (say, up to a few hundred), and it only requires the combinatorial reasoning from Hints 1–5 — no clever structure beyond “try everything”.

Now we refine. Observe: if you extend $s[i..j]$ by one more character (making it $s[i..j+1]$), the new string is a strict extension of the old one, so it is lex $\ge$ the old one (strict if the old was non-empty).

Therefore, for a fixed start $i$, pushing $j$ as far right as feasibility allows can only help — longer is always at least as good.

What’s the largest $j$ that’s feasible for a given $i$? Constraint 4 from Hint 5 says $\lfloor i/l \rfloor + \lfloor (n-1-j)/l \rfloor \ge k-1$, i.e.

So the max feasible $j$ given $i$ is:

(If the prefix alone already has enough room for $k-1$ length-$l$ parts, we take no right parts and $\mathrm{rp}(i) = n-1$.)

Answer to Hint 7:

For a fixed start $i$, the best feasible candidate is always $s[i..\mathrm{rp}(i)]$ (any feasible $(i, j)$ with $j < \mathrm{rp}(i)$ is a prefix of $s[i..\mathrm{rp}(i)]$, hence lex $\le$).

So out of the $O(n^2)$ pairs the brute force tried, only $O(n)$ survive: one per valid start $i$. The valid starts are:

• $i = 0$ (initial candidate $s[0..n-1-(k-1)l]$),
• $i \in [l,\; n-l]$ with $\mathrm{rp}(i) - i + 1 \ge l$.

Pseudocode:

best = s[0..n-1-(k-1)*l]
for i = l..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 best: best = s[i..rp]
print best

Each iteration still needs an $O(n)$ lex comparison, so the total is $O(n^2)$ — one factor of $n$ saved over the brute force.

For $i \in [1, l-1]$ the prefix $s[0..i-1]$ is too short for even a single length-$\ge l$ part — so $(i, j)$ can never be feasible. That’s precisely the “impossible” case in Hint 3.

The iteration therefore handles $i = 0$ explicitly (as the initial best) and jumps to $i = l, l+1, \ldots, n-l$.

If $i$ is large enough that $\lfloor i/l \rfloor \ge k - 1$, the prefix alone already has room for all required parts, so $r = \max(k-1-m, 0) = 0$ and the candidate extends all the way to $n-1$:

In code: clamp $r \ge 0$, or equivalently clamp $\mathrm{rp}(i) \le n - 1$. Either works; the reference solutions just use the clamp.

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

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

Sweep $i = 2,\ldots,9$:

• $i=2$: $m=1,\,r=3,\,\mathrm{rp}=4 \Rightarrow$ candidate $\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 of it).

Answer: $\text{rac}$. Matches the sample.

The $O(n^2)$ algorithm is correct; the remaining cost is the $O(n)$ substring comparison inside the loop.

A suffix array plus LCP array plus a sparse table over the LCP array supports $O(1)$ lex comparison of any two substrings after $O(n \log n)$ preprocessing. Plugging that in gives $O(n \log n)$ per test case, which is what the model solution does.

You do not need suffix arrays / LCP to understand this problem — the $O(n^3)$ brute force and its $O(n^2)$ refinement already contain all of the combinatorial ideas. SA + LCP is only a speed-up for the comparison step at the end.