source: http://careercup.com/question?id=4855286160424960
Given a random string S and another string T with unique elements,. find the minimum consecutive sub-string of S such that it contains all the elements in T
example:
S=’adobecodebanc’
T=’abc’
answer=’banc”
The idea is to maintain a double-linked-list. For each character in T, there is an element in double-linked-list. Every time, head has the indicates where window start. Tail indicates where window end. For string T, initialize double-linked-list like below:
a b c
-1 -1 -1
Then, for each character in S, find its element in double-linked-list, update element position, and move it to list tail. Then new window starts at head.pos, window ends at tail.pos. Check if window size is less than current one. The process is like below:
check my code on github: link