HackerRank : Week of Code 33 – Pattern Count

By | June 14, 2017
Pattern Count: Hackerrank

A string s contains many patterns of the form 1(0+)1 where (0+) represents any non-empty consecutive sequence of 0 ‘s. The patterns are allowed to overlap.

For example, consider string “1101001”, we can see there are two consecutive sequences “1(0)1” and “1(00)1” which are of the form  1(0+)1.

image

You have to answer q queries, each containing a string s. For each query, find and print the total number of patterns of the form 1(0+)1  that occur in s .

Input Format

The first line contains a single integer , denoting the number of queries. After that, lines follow. The of them represents the test case and contains a string for this test case.

Output Format

Output exactly lines, one for each testcase.

Sample Input 0

3
100001abc101
1001ab010abc01001
1001010001

Sample Output 0

2
2
3
Solution
Hint: Pretty easy problem. I have used regex to find and replace patterns.