Sort 9 Discussions, By:
Please Login in order to post a comment
Solved this problem in O(T log T). For those seeking hints: one can look at this problem as being a graph problem, in which each letter is a Node and "letter X has to occur before letter Y in the passcode" is a directed edge from X to Y. You can then repeatedly take the lexicographically smallest letter with in-degree zero (this will be the next letter in the passcode) and remove it from the graph. If there is no letter with in-degree zero, then something is wrong.
By using the right data structures, you can do this in O(E log E) where E is the number of edges in the graph.
Let me know if you solved this problem in a completely different way, I'm curious!
in the sample 1, why TSMHWRONG is not a possible password? Given that input, how do you know that T comes after SM?
can someone please upload hrer a few test cases and res?
I solved this problem using mathematica and graph theory,
too bad I can't use it here..
My code is not pretty, but it worked, and despite being O(v^3) where v is the number of distinct characters in the logins, it's fast --- all testcases run in 0.05 s or less.