# Count ways to partition a Binary String such that each substring contains exactly two 0s

Given binary string **str**, the task is to find the count of ways to partition the string such that each partitioned substring contains exactly two **0**s.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:str = “00100”Output:2Explanation:

Possible ways to partition the string such that each partition contains exactly two0s are: { {“00”, “100”}, {“001”, “00”} }.

Therefore, the required output is 2.

Input:str = “000”Output:0

**Approach:** The idea is to calculate the count of **1**s between every two consecutive **0**s of the given string. Follow the steps below to solve the problem:

- Initialize an array, say
**IdxOf0s[]**, to store the indices of**0**s in the given string. - Iterate over the characters of the given string and store the indices of the 0s into
**IdxOf0s[]**. - Initialize a variable, say
**cntWays**, to store the count of ways to partition the string such that each partition contains exactly two**0**s. - If the count of
**0**s in the given string is odd, then update**cntWays = 0**. - Otherwise, traverse the array
**IdxOf0s[]**and calculate the count of ways to partition the array having each partition exactly two**0**s using**cntWays *= (IdxOf0s[i] – IdxOf0s[i – 1])** - Finally, print the value of
**cntWays**.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to find count of ways to partition` `// the string such that each partition` `// contains exactly two 0s.` `int` `totalWays(` `int` `n, string str)` `{` ` ` `// Stores indices of 0s in` ` ` `// the given string.` ` ` `vector<` `int` `> IdxOf0s;` ` ` `// Store the count of ways to partition` ` ` `// the string such that each partition` ` ` `// contains exactly two 0s.` ` ` `int` `cntWays = 1;` ` ` `// Iterate over each characters` ` ` `// of the given string` ` ` `for` `(` `int` `i = 0; i < n; i++) {` ` ` `// If current character is '0'` ` ` `if` `(str[i] == ` `'0'` `) {` ` ` `// Insert index` ` ` `IdxOf0s.push_back(i);` ` ` `}` ` ` `}` ` ` `// Stores total count of 0s in str` ` ` `int` `M = IdxOf0s.size();` ` ` `if` `(M == 0 or M % 2) {` ` ` `return` `0;` ` ` `}` ` ` `// Traverse the array, IdxOf0s[]` ` ` `for` `(` `int` `i = 2; i < M; i += 2) {` ` ` `// Update cntWays` ` ` `cntWays = cntWays * (IdxOf0s[i]` ` ` `- IdxOf0s[i - 1]);` ` ` `}` ` ` `return` `cntWays;` `}` `// Driver Code` `int` `main()` `{` ` ` `string str = ` `"00100"` `;` ` ` `int` `n = str.length();` ` ` `cout << totalWays(n, str);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.util.*;` `class` `GFG` `{` ` ` `// Function to find count of ways to partition` `// the string such that each partition` `// contains exactly two 0s.` `static` `int` `totalWays(` `int` `n, String str)` `{` ` ` ` ` `// Stores indices of 0s in` ` ` `// the given string.` ` ` `ArrayList<Integer> IdxOf0s = ` ` ` `new` `ArrayList<Integer>();` ` ` ` ` `// Store the count of ways to partition` ` ` `// the string such that each partition` ` ` `// contains exactly two 0s.` ` ` `int` `cntWays = ` `1` `;` ` ` ` ` `// Iterate over each characters` ` ` `// of the given string` ` ` `for` `(` `int` `i = ` `0` `; i < n; i++)` ` ` `{` ` ` ` ` `// If current character is '0'` ` ` `if` `(str.charAt(i) == ` `'0'` `)` ` ` `{` ` ` ` ` `// Insert index` ` ` `IdxOf0s.add(i);` ` ` `}` ` ` `}` ` ` ` ` `// Stores total count of 0s in str` ` ` `int` `M = IdxOf0s.size();` ` ` `if` `((M == ` `0` `) || ((M % ` `2` `) != ` `0` `))` ` ` `{` ` ` `return` `0` `;` ` ` `}` ` ` ` ` `// Traverse the array, IdxOf0s[]` ` ` `for` `(` `int` `i = ` `2` `; i < M; i += ` `2` `)` ` ` `{` ` ` ` ` `// Update cntWays` ` ` `cntWays = cntWays * (IdxOf0s.get(i)` ` ` `- IdxOf0s.get(i - ` `1` `));` ` ` `} ` ` ` `return` `cntWays;` `}` ` ` `// Driver code` `public` `static` `void` `main(String[] args)` `{` ` ` `String str = ` `"00100"` `;` ` ` `int` `n = str.length();` ` ` `System.out.print(totalWays(n, str));` `}` `}` `// This code is contributed by sanjoy_62.` |

## Python3

`# Python3 program for the above approach` `# Function to find count of ways to partition` `# thesuch that each partition` `# contains exactly two 0s.` `def` `totalWays(n, ` `str` `):` ` ` ` ` `# Stores indices of 0s in` ` ` `# the given string.` ` ` `IdxOf0s ` `=` `[]` ` ` `# Store the count of ways to partition` ` ` `# the such that each partition` ` ` `# contains exactly two 0s.` ` ` `cntWays ` `=` `1` ` ` `# Iterate over each characters` ` ` `# of the given string` ` ` `for` `i ` `in` `range` `(n):` ` ` ` ` `# If current character is '0'` ` ` `if` `(` `str` `[i] ` `=` `=` `'0'` `):` ` ` ` ` `# Insert index` ` ` `IdxOf0s.append(i)` ` ` `# Stores total count of 0s in str` ` ` `M ` `=` `len` `(IdxOf0s)` ` ` `if` `(M ` `=` `=` `0` `or` `M ` `%` `2` `):` ` ` `return` `0` ` ` `# Traverse the array, IdxOf0s[]` ` ` `for` `i ` `in` `range` `(` `2` `, M, ` `2` `):` ` ` ` ` `# Update cntWays` ` ` `cntWays ` `=` `cntWays ` `*` `(IdxOf0s[i] ` `-` ` ` `IdxOf0s[i ` `-` `1` `])` ` ` `return` `cntWays` `# Driver Code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` ` ` `str` `=` `"00100"` ` ` `n ` `=` `len` `(` `str` `)` ` ` ` ` `print` `(totalWays(n, ` `str` `))` `# This code is contributed by mohit kumar 29` |

## C#

`// C# program for the above approach` `using` `System;` `using` `System.Collections; ` `using` `System.Collections.Generic; ` `class` `GFG` `{` ` ` `// Function to find count of ways to partition` ` ` `// the string such that each partition` ` ` `// contains exactly two 0s.` ` ` `static` `int` `totalWays(` `int` `n, ` `string` `str)` ` ` `{` ` ` `// Stores indices of 0s in` ` ` `// the given string.` ` ` `ArrayList IdxOf0s` ` ` `= ` `new` `ArrayList();` ` ` `// Store the count of ways to partition` ` ` `// the string such that each partition` ` ` `// contains exactly two 0s.` ` ` `int` `cntWays = 1;` ` ` `// Iterate over each characters` ` ` `// of the given string` ` ` `for` `(` `int` `i = 0; i < n; i++)` ` ` `{` ` ` `// If current character is '0'` ` ` `if` `(str[i] == ` `'0'` `)` ` ` `{` ` ` `// Insert index` ` ` `IdxOf0s.Add(i);` ` ` `}` ` ` `}` ` ` `// Stores total count of 0s in str` ` ` `int` `M = IdxOf0s.Count;` ` ` `if` `((M == 0) || ((M % 2) != 0)) {` ` ` `return` `0;` ` ` `}` ` ` `// Traverse the array, IdxOf0s[]` ` ` `for` `(` `int` `i = 2; i < M; i += 2)` ` ` `{` ` ` `// Update cntWays` ` ` `cntWays = cntWays * (Convert.ToInt32(IdxOf0s[i]) -` ` ` `Convert.ToInt32(IdxOf0s[i - 1]));` ` ` `}` ` ` `return` `cntWays;` ` ` `}` ` ` `// Driver code` ` ` `static` `public` `void` `Main()` ` ` `{` ` ` `string` `str = ` `"00100"` `;` ` ` `int` `n = str.Length;` ` ` `Console.Write(totalWays(n, str));` ` ` `}` `}` `// This code is contributed by Dharanendra L V` |

## Javascript

`<script>` `// Javascript program for the above approach` `// Function to find count of ways to partition` `// the string such that each partition` `// contains exactly two 0s.` `function` `totalWays(n, str)` `{` ` ` `// Stores indices of 0s in` ` ` `// the given string.` ` ` `var` `IdxOf0s = [];` ` ` `// Store the count of ways to partition` ` ` `// the string such that each partition` ` ` `// contains exactly two 0s.` ` ` `var` `cntWays = 1;` ` ` `// Iterate over each characters` ` ` `// of the given string` ` ` `for` `(` `var` `i = 0; i < n; i++) {` ` ` `// If current character is '0'` ` ` `if` `(str[i] == ` `'0'` `) {` ` ` `// Insert index` ` ` `IdxOf0s.push(i);` ` ` `}` ` ` `}` ` ` `// Stores total count of 0s in str` ` ` `var` `M = IdxOf0s.length;` ` ` `if` `(M == 0 || M % 2) {` ` ` `return` `0;` ` ` `}` ` ` `// Traverse the array, IdxOf0s[]` ` ` `for` `(` `var` `i = 2; i < M; i += 2) {` ` ` `// Update cntWays` ` ` `cntWays = cntWays * (IdxOf0s[i]` ` ` `- IdxOf0s[i - 1]);` ` ` `}` ` ` `return` `cntWays;` `}` `// Driver Code` `var` `str = ` `"00100"` `;` `var` `n = str.length;` `document.write( totalWays(n, str));` `</script>` |

**Output:**

2

**Time Complexity:** O(N)**Auxiliary Space:** O(N)