I believe a constant solution exists, because Fizzbuzz repeats after 8 items. Still working on it...
<EDIT>
Yes, here's a constant solution: http://codepad.org/Id9eu0Ax
<EDIT>
Yes, here's a constant solution: http://codepad.org/Id9eu0Ax
For any sequence containing fizzbuzz, match up the fizzbuzz with 15 and you're done. Any sequence of length >=7, fizzbuzz will be present. Thus, we only need to think about sequences length <7 that don't contain fizzbuzz. Solving this by brute force is constant time, since you only have finite possible inputs.
It's O(1) to find a candidate solution, but of course it will still be O(N) to verify that the solution really works.
Are you sure? I don't think the challenge said the sequence could not be gappy.
For your example a shorter one would be 9,10,15.
raw_input = ["Fizz","Buzz","Fizz","Fizz","Buzz","Fizz","FizzBuzz","Buzz","Buzz"]