# 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^{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.