Lexicographically Smallest String Problem Statement: Given a string/pattern only consisting of '&lt;' and '&gt;' symbol, find the lexicographically smallest string that satisfies the pattern(made up of only lowercase english alphabets). Some examples are given below for better understanding.
Examples:

Input(String) - '&gt;&gt;'
Output(String) - 'cba' (because c &gt; b &gt; a)
Input(String) - '&gt;'
Output(String) - 'ba' (because b &gt; a)
Input(String) - '&gt;&lt;&gt;'
Output(String) - 'badc' (because b &gt; a &lt; d &gt; c)

Constraints: String/Pattern length is always &lt;= 25 and in the output string, no alphabet should be repeated.
I am unable to come up with any approach which has a lesser complexity than O(N!)(which would surely never pass the time limits), N being the given string/pattern's length. Any help is appreciated.
P.S. - This problem was asked in a HackerEarth hiring contest, and no, the contest is no longer live.
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.