I recently had an interview with a local to Phoenix company, and of their question really messed me up :)
Assuming we have a sentence

a cat in a hat

and a substring

at

find the number of occurences of the substring in the sentence, given the fact that characters in the sentence might not be adjancent but must have same order as in substring.

For the above sample we would have
a[0] with all t - 2
a[3] with all t - 2
a[9] with all t - 1
a[12] with all t - 1
which makes the final answer 6

for a substring if length 2 might be simple, but it gets quite complex with longer substrings.

Now even sure where to start with this :)

Ideas?