shortest digest of a string
- by meta
[Description]
Given a string of char type, find a shortest digest, which is defined as: a shortest sub-string which contains all the characters in the original string.
[Example]
A = "aaabedacd"
B = "bedac" is the answer.
[My solution]
Define an integer table with 256 elements, which is used to record the occurring times for each kind of character in the current sub-string.
Scan the whole string, statistic the total kinds of character in the given string by using the above table.
Use two pointers, start, end, which are initially pointing to the start and (start + 1) of the given string. The current kinds of character is 1.
Expand sub-string[start, end) at the end until it contains all kinds of character. Update the shortest digest if possible.
Contract sub-string[start, end] at the start by one character each time, try to restore its digest property if necessary by step 4.
The time cost is O(n), and the extra space cost is constant.
Any better solution without extra space?
