Tuesday, June 10, 2014

Continuous sequence

This problem is from codeforces. If you want to solve this problem on your own. Please head over here and solve it!

The simplified problem statement is as follows.


Given a sequence of 0 and 1s. Check if contains a continuous sequence of 0/1 of length 7.

For example see some input output combinations

Input                             Output
------------------------------------------
10001010010011                    NO
1000000001100                     YES
000111111111110                   YES

Your program should accept a sequence of 0, 1s as input and print YES of there is a sequence of 7 0/1s in it or NO if does not contain such a sequence.


The algorithm is as follows.


We maintain a state variable to see if we are getting a sequence 0s or sequence of 1s. We also use a continuity counter to track the maximum number of similar symbols. If this counter reaches 7 anytime we break and declare the result as YES.


If we finish processing the input without the counter reaching 7 anytime, we output the result as NO.

Here is the C++ implementation of the above algorithm.