1
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.