algorithms – 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 < cdots < a_n$. If $w$ equals $>^{n-1}$ then clearly the solution is $a_n a_{n-1} ldots a_1$. If $w$ starts with a run of $ell$ many $>$‘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(>^ell<x,{a_1,ldots,a_n})=a_{ell+1}ldots a_1 s(x,{a_{ell+2},ldots,a_n}), quad s(>^{n-1},{a_1,ldots,a_n}) = a_n ldots a_1.
$$

Since this greedy construction always “eats away” a prefix of the alphabet, it can easily be implemented in linear time.