# Find all the patterns of “1(0+)1” in a given string | SET 1(General Approach)

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

Note : It contains digits and lowercase characters only. The string is not necessarily a binary. 100201 is not a valid pattern.
One approach to solve the problem is discussed here, other using Regular expressions is given in Set 2
Examples:

```Input : 1101001
Output : 2

Input : 100001abc101
Output : 2
```

Let size of input string be n.
1. Iterate through index ‘0’ to ‘n-1’.
2. If we encounter a ‘1’, we iterate till the elements are ‘0’.
3. After the stream of zeros ends, we check whether we encounter a ‘1’ or not.
4. Keep on doing this till we reach the end of string.

Below is the implementation of the above method.

## C++

br>
 `/* Code to count 1(0+)1 patterns in a string */` `#include ` `using` `namespace` `std; ` ` `  `/* Function to count patterns */` `int` `patternCount(string str) ` `{ ` `    ``/* Variable to store the last character*/` `    ``char` `last = str[0]; ` ` `  `    ``int` `i = 1, counter = 0; ` `    ``while` `(i < str.size()) ` `    ``{ ` `        ``/* We found 0 and last character was '1', ` `          ``state change*/` `        ``if` `(str[i] == ``'0'` `&& last == ``'1'``) ` `        ``{ ` `            ``while` `(str[i] == ``'0'``) ` `                ``i++; ` ` `  `            ``/* After the stream of 0's, we got a '1', ` `               ``counter incremented*/` `            ``if` `(str[i] == ``'1'``) ` `                ``counter++; ` `        ``} ` ` `  `        ``/* Last character stored */` `        ``last = str[i]; ` `        ``i++; ` `    ``} ` ` `  `    ``return` `counter; ` `} ` ` `  `/* Driver Code */` `int` `main() ` `{ ` `    ``string str = ``"1001ab010abc01001"``; ` `    ``cout << patternCount(str) << endl; ` `    ``return` `0; ` `} `

## Java

 `// Java Code to count 1(0+)1  ` `// patterns in a string  ` `import` `java.io.*; ` ` `  `class` `GFG  ` `{ ` `    ``// Function to count patterns  ` `    ``static` `int` `patternCount(String str) ` `    ``{ ` `        ``/* Variable to store the last character*/` `        ``char` `last = str.charAt(``0``); ` `     `  `        ``int` `i = ``1``, counter = ``0``; ` `        ``while` `(i < str.length()) ` `        ``{ ` `            ``/* We found 0 and last character was '1', ` `            ``state change*/` `            ``if` `(str.charAt(i) == ``'0'` `&& last == ``'1'``) ` `            ``{ ` `                ``while` `(str.charAt(i) == ``'0'``) ` `                    ``i++; ` `     `  `                ``// After the stream of 0's, we  ` `                ``// got a '1',counter incremented ` `                ``if` `(str.charAt(i) == ``'1'``) ` `                    ``counter++; ` `            ``} ` `     `  `            ``/* Last character stored */` `            ``last = str.charAt(i); ` `            ``i++; ` `        ``} ` `     `  `        ``return` `counter; ` `    ``} ` `     `  `    ``// Driver Code  ` `    ``public` `static` `void` `main (String[] args) ` `    ``{ ` `        ``String str = ``"1001ab010abc01001"``; ` `        ``System.out.println(patternCount(str)); ` `         `  `    ``} ` `} ` ` `  `// This code is contributed by vt_m. `

## Python3

 `# Python3 code to count 1(0+)1 patterns in a  ` ` `  `# Function to count patterns  ` `def` `patternCount(``str``): ` `     `  `    ``# Variable to store the last character ` `    ``last ``=` `str``[``0``] ` ` `  `    ``i ``=` `1``; counter ``=` `0` `    ``while` `(i < ``len``(``str``)): ` `         `  `        ``# We found 0 and last character was '1', ` `        ``# state change ` `        ``if` `(``str``[i] ``=``=` `'0'` `and` `last ``=``=` `'1'``): ` `            ``while` `(``str``[i] ``=``=` `'0'``): ` `                ``i ``+``=` `1` `                 `  `                ``# After the stream of 0's, we got a '1', ` `                ``# counter incremented ` `                ``if` `(``str``[i] ``=``=` `'1'``):  ` `                    ``counter ``+``=` `1` `         `  `        ``# Last character stored  ` `        ``last ``=` `str``[i] ` `        ``i ``+``=` `1` `     `  `    ``return` `counter ` ` `  ` `  `# Driver Code  ` `str` `=` `"1001ab010abc01001"` `ans ``=` `patternCount(``str``) ` `print` `(ans) ` `     `  `# This code is contributed by saloni1297 `

## C#

 `// C# Code to count 1(0 + )1  ` `// patterns in a string  ` `using` `System; ` ` `  `class` `GFG  ` `{ ` `     `  `    ``// Function to count patterns  ` `    ``static` `int` `patternCount(String str) ` `    ``{ ` `        ``// Variable to store the  ` `        ``// last character ` `        ``char` `last = str[0]; ` `     `  `        ``int` `i = 1, counter = 0; ` `        ``while` `(i < str.Length) ` `        ``{ ` `            ``// We found 0 and last  ` `            ``// character was '1', ` `            ``// state change ` `            ``if` `(str[i] == ``'0'` `&& last == ``'1'``) ` `            ``{ ` `                ``while` `(str[i] == ``'0'``) ` `                    ``i++; ` `     `  `                ``// After the stream of 0's, we  ` `                ``// got a '1',counter incremented ` `                ``if` `(str[i] == ``'1'``) ` `                    ``counter++; ` `            ``} ` `     `  `            ``// Last character stored  ` `            ``last = str[i]; ` `            ``i++; ` `        ``} ` `     `  `        ``return` `counter; ` `    ``} ` `     `  `    ``// Driver Code  ` `    ``public` `static` `void` `Main () ` `    ``{ ` `        ``String str = ``"1001ab010abc01001"``; ` `        ``Console.Write(patternCount(str)); ` `         `  `    ``} ` `} ` ` `  `// This code is contributed by nitin mittal `

## PHP

 ` `

Output :

```2
```