HackerRank: string algorithm - Reverse Shuffle Merge (IV)

April 3, 2016


C# solution:

https://gist.github.com/jianminchen/346970ad058d64041ab7b8cbe9ecb495

Read the code, and talk about the ideas:
Best way to explain the algorithm - greedy one, the following, is to take away reverse, and also merge two parts (these are noisy!), work on a string, simple test case, how to construct a string with minimum lexically value, using stack to do greedy design, and also allow the back and forth two ways to optimize.

Here is the simple example:
1. string a2b2c2, for example, aabbcc, so abc is shortest one.
For string bbccaa,
first b, put in stack, second b, have to skip; and then, c is coming,
'c' > 'b', push c to stack, so stack is like this
b
c
and then, second c, skip it; now 'a' is coming,
'a' is bigger than 'b', but b does have any number to skip; need to put 'a' in anyhow.

the output will be "bca";

2. Try another one:
babcac
First one, b, go into the stack:
b,
meet a, and then, 'a' <'b', because b still have one to skip, so pop out b, skip the b, push 'a' in the stack;
Now, another b is coming, we have to hold one b in output, push it in the stack:
b
a
And then, c is coming, push it in c.
c
b
a

Now, a is coming, skip it; c is coming, also skip it.

the result is 'abc', smallest one in lexical sense.

3. Try third one:
work on first test case, make small change. move bbccaa, one of b, so the string is ccbaab,
c - put in the stack
c - skip it.
b - compare to stack top, b ( b has one left to skip);
so b into stack
b
c

c- second c, skip it
a- compare to the stack top: b
'a'<'b', still 'b' can skip one, one more is coming
pop up b, push a in,
a
c
and then, last char 'b' into stack
b
a
c
the output is "cab"

The question is to ask yourself, do you have genius to design it at the beginning, called thinking about in stack to cover mistake in greedy approach! Julia has no clue right now, she spent 9 hours to take this lesson. Backtracking is better term for using stack in the design.

April 5, 2016
Go over a2b2c2 case, the lexical smallest substring (Julia's first practice):
bccaba,
visit first 'b', skip 'b', because a has 2 of them to visit
visit first 'c', skip 'c',
visit second 'c', cannot skip, has to take it. Now, best one is starting from c, of course it is worse than the one starting from 'b', such as "bca".

So, greedy algorithm is to take what ever you can, and then, backtracking, make it smaller iteratively.
--
code source:  a box employee