Pretty String

Let $L=|S|$. If there are $k$ lines, their lengths are $1,1+n,\ldots,1+(k-1)n$, so

$$L=k+n\frac{k(k-1)}2.$$

For $k\geq2$, set $D=k(k-1)/2$. A split exists exactly when $L-k$ is a positive multiple of , and then .

Since $n\geq1$, we need $k(k+1)/2\leq L$. Check such values of $k$ from largest to smallest and choose the first valid one. Then print consecutive pieces of $S$ of lengths . A single line is possible only when , so a string of length has no answer.

There are $O(\sqrt L)$ candidate values of $k$, and printing takes $O(L)$ time. Space usage including the input string is .

Solution written by GPT6