NABILHACKER - Hack the Password
Many people asked me what actually contest programming do in real life projects. That does not feel so interesting to me. What I found interesting is, one day a hacker friend came to me. He asked me to solve one of his hacking problems.
When you try to steal someone's password, you may set a keylogger in his/her computer. Keylogger will give you a string that is typed as the password. But there is a problem, it will give you everything victim typed such as left key, right key, backspace everything. (Left key and right key means the keys you use to play car games, and backspace is the key you use to remove a letter, the button on the top of "Enter" button. )
Suppose, the victim typed "generio312" as password, but he follows these criteria:
1. he typed generio1.
2. Then he pressed the left key, and press 3. So the password will be generio31.
3. Then he pressed the right key and press 2. So the password will be generio312.
4. Now he typed ghj and then press backspace three times and remove these three letters. So the final password is generio312.
But, as I said, keylogger gives you all the typed key. You will get "generio1<3>2ghj---". (Here, < for left key, > for right key and - for backspace.)
At first input T, the number of test cases.
Then input T strings. 1<=|s|<=10^6. The strings will include upper case, lower case, <, >, - and digits(0-9).
The output should contain a string each line, the password.
I'm using Go and TLE for O(n).
i love stack <3
@kaushalag29 O I found your solution. insert and erase in vectors take O(n) complexity, so your complexity is technically O(n^2) (I assume). Instead of insert and delete, please try to use push_back and pop_back.
@kaushalag29 Which one is your solution? O(n) must get AC.
Do we assume that ">>" (right key) at the START of an expression are redundant as in most textfields these days??
@Nabil: O(n) gives TLE?What is the expected time complexity?