Lexicographically Smallest String

Question

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.

Answer 1

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.