# Lexicographically Smallest String

Problem Statement: Given a string/pattern only consisting of '<' and '>' 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:

1. Input(String) - '>>'
Output(String) - 'cba' (because c > b > a)
2. Input(String) - '>'
Output(String) - 'ba' (because b > a)
3. Input(String) - '><>'
Output(String) - 'badc' (because b > a < d > c)

Constraints: String/Pattern length is always <= 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 < \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.