Lexicographically Smallest String
Let us denote the solution for a string $w$ and a set $A$ of remaining letters by $s(w,A)$. Also let $A = a_1 &lt; \cdots &lt; a_n$. If $w$ equals $&gt;^{n-1}$ then clearly the solution is $a_n a_{n-1} \ldots a_1$. If $w$ starts with a run of $\ell$ many $&gt;$'s (possibly $\ell=0$), then the first $\ell+1$ letters of any solution must be $a_{\ell+1} \ldots a_1$ or lexicographically larger. Conversely, there always is such a solution – we can construct one recursively. This shows that
$$
 s(&gt;^\ell&lt;x,\{a_1,\ldots,a_n\})=a_{\ell+1}\ldots a_1 s(x,\{a_{\ell+2},\ldots,a_n\}), \quad s(&gt;^{n-1},\{a_1,\ldots,a_n\}) = a_n \ldots a_1.
$$
Since this greedy construction always &quot;eats away&quot; a prefix of the alphabet, it can easily be implemented in linear time.