CareerCup

magic, it works

OMG, I finally found the solution for all test cases in this page:
combine my approach #1 with left to right pass
with #2 with right to left pass
than compare results.

But I am still not sure in the result, because may exist a test case which breaks down things.

Hi, I came up with almost the same approach and it works. But my version works fine with test case "bcabc" and returns "abc", because of another way of comparison.
Please find on this page Ctrl+F -> manzhos.max
it would be my post with details

Well, this comment of user @can
"Tried "cacasc" with krutin's C++ code, and it does NOT produce the correct answer. It outputs "asc" instead of "acs"."
killed my approach :(

Second test case should be:
1) ____c
2) ___bc
3) __abc
4) _cabc -> abc
5) _babc -> abc

O(n) preprocessing (time and memory)
O(n) building a solution (time and memory)
So idea is in usage of dynamic programming.
Let's consider an example.
"cbacdcbc"
my first approach was in building new string character by character i.e.
1) c
2) cb
3) cba
4) cbac (aha! duplicate. now let's choose the letter to remove)
4.1) cba > bac, so we choose bac
4.2) for easiness of comparison I used a condition "if earliar (leftmost) duplicate next character
is less than current character then remove earlier occurrence else remove the last character".
In example firstC.next = 'b', 'b' < 'c', remove earlier 'c'
5) bac -> bacd
6) bacd -> bacdc -> bacd
7) bacd -> bacdb -> acdb
8) acdb -> acdbc -> acdb
9) acdb is an answer

Well, it doesn't work with "bcabc", because it would return "bac",
but good news! A simple alrorithm improvement solves this problem, just go from end to the begininng!
It is the only right way to do it, because lexigraphically a string becomes heavier in this order (from right to left), if we consider formula like
"bac" = 2*10^2 + 1*10 + 3

So okay, let's test it with vice-versa approach

test case "bcabc", excpected result "abc"
1) c
2) bc
3) abc
4) cabc -> abc
5) babc -> abc

So approach is doing fine!
Now there are 2 problems:
1) Comparison of examples.
It might be O(n) very for every comparison, but with approach described in the above list in paragraph 4.2 it is O(1)
2) Looking for and removing duplicaes.
Which is even O(n^2) in worst case. So here we should use preprocessing. What kind?
HashMap<Character, LinkedList<Integer>> - linkedlist of character occurences in the array from right to left.
So we could check every insertion of character to out resulting string in O(1) with preprocessed usage of memory in O(n)

I will write a code soon.