The contestant should note that any solution that actually tries to match every possible permutation of ~W~ within ~S~ is doomed to failure. Even with a small alphabet, the total number of permutations for ~W~ is very big. An optimal solution should take into account the fact that we are looking for every possible permutation of ~W~, in other words, we don't care for the order of the characters.

OPTIMAL SOLUTION: The optimal solution uses a queue where it pushes consecutive characters of ~S~ until an error condition is reached. An error condition is reached whenever:

• A character ~c~ that does not appear in ~W~ is in the queue.
• The number of times a character ~c~, that appears in ~W~, is in the queue exceeds the number of times that character appears in ~W~.

After an error condition is reached, characters are popped from the queue until the error condition is cleared. In order to check for an error condition, the optimal solution keeps two vectors of length equal to the alphabet, each entry corresponds to a character in the alphabet. These two vectors maintain the number of times each character appears in ~W~ and the number of times each character is in the queue. Whenever you push or pop a character from the queue, the entry for that character must be checked in both vectors.

If at any time the length of the queue is equal to the length of ~W~ without having an error condition, then you have found a match.

Since every character in ~S~ is pushed and popped once into the queue, the complexity of the resulting algorithm is ~\mathcal O(S)~.

SOLUTION 2: Instead of keeping two vectors to check for an error condition, every time a character is pushed or popped from the queue check every character in the alphabet to catch an error condition. This solution yields a complexity ~\mathcal O(S \Sigma)~ and should be able to score 70 points.

SOLUTION 3: Starting from every position in ~S~, look for a match by checking the number of times each character appears in ~W~, if an error is found, stop an advance to the next position in ~S~. This solution can yield a worst case complexity of ~\mathcal O(S^2)~ and scored between 50 and 65 points depending on the implementation.