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.
- Input(String) - '>>'
Output(String) - 'cba' (because c > b > a)
- Input(String) - '>'
Output(String) - 'ba' (because b > a)
- 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.