Feature
substring can be thought as a feature, this kind of question is asking for find that feature in a string.
Not order related
https://www.lintcode.com/problem/minimum-window-substring/description
https://www.lintcode.com/submission/17057235/
It asks to find a shorted substring that contains all characters in target string. Here the feature is the counts of characters in target string, since order does not matter.
To solve this kind of problem, you will need two piece of data:
1. the feature, a statistics of characters in target string. it is counting in this problem
counters can be a hashmap or int array if character set is small and known.
2. a number that denotes if all unique characters has been processed. Every time when there is a match on a character's count, increase unique number count. When the total unique character counts are equal, it finds one window.
Algorithm:
1. calculate feature
2.check feature in string.
2.1. To find feature string in a string, consider to use two pointers, Fix left position the first, run the right pointer to find a substring that covers the feature.
2.2 when a substring containing the feature was found, change window by advance the left pointer
2.3 track the shortest substring that has the feature
2.4 continue 2.1 to find next substring that covers the feature
