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 0s.
Examples:
Input: str = “00100”
Output: 2
Explanation:
Possible ways to partition the string such that each partition contains exactly two 0s 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 1s between every two consecutive 0s of the given string. Follow the steps below to solve the problem:
- Initialize an array, say IdxOf0s[], to store the indices of 0s 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 0s.
- If the count of 0s 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 0s 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 Codeint 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 codepublic 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 Codeif __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 Codevar str = "00100";var n = str.length;document.write( totalWays(n, str));</script> |
Output:
2
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
