Count Substrings with number of 0s and 1s in ratio of X : Y
Given a binary string S, the task is to count the substrings having the number of 0s and 1s in the ratio of X : Y
Examples:
Input: S = “010011010100”, X = 3, Y = 2
Output: 5
Explanation: The index range for the 5 substrings are:
(0, 4), (2, 6), (6, 10), (7, 11), (2, 11)Input: S = “10010101”, X = 1, Y = 2
Output: 2
Naive Approach:
The Naive approach for the problem would be to find all the substrings and check whether the number of 0s and 1s are in ratio X : Y using the prefix sum concept.
Time Complexity: O(N2).
Auxiliary Space: O(N)
Efficient Approach:
The problem can be solved using this idea:
Create a new array where all the 0s are -Y and all 1s are X. Now whenever 0s : 1s = X : Y, then in new array the sum of count of 0s and 1s would be c * X * -Y + c * Y * X = 0, where c is a constant not equal to 0.
Follow the steps to solve this problem using the efficient approach:
- Create a new array from the binary string, where for each 0 in the binary string there is -Y in the new array and for each 1 there is X.
- Now find the number of subarrays of the new array which have the sum of values = 0, using the concept in this article: Number of subarrays having sum exactly equal to k
- Return the count of subarrays obtained.
Below is the implementation of this approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find number of subarrays // with sum equal to 0. int CountSubStringsWithZeroSum(vector< int >& arr) { int n = arr.size(); // Creating default dictionary with default val zero. // It stores the count of previous subarrays sum // from 0 to i for every i in range(0, curr_index-1) unordered_map< int , int > prevSum; int count = 0; int currsum = 0; for ( int i = 0; i < n; i++) { currsum += arr[i]; if (currsum == 0) count += 1; if (prevSum.find(currsum) != prevSum.end()) count += prevSum[currsum]; prevSum[currsum] += 1; } return count; } // Function to count subarrays with // number of 0's and 1's in ratio of X:Y int countSubStringsWith01InRatioXY(string& S, int X, int Y) { // First change 0's to -Y 1's to X vector< int > arr; for ( auto i : S) { if (i == '0' ) arr.push_back(-Y); else arr.push_back(X); } return CountSubStringsWithZeroSum(arr); } // Driver Code int main() { string S = "010011010100" ; int X = 3; int Y = 2; // Function Call cout << countSubStringsWith01InRatioXY(S, X, Y); return 0; } // This code is contributed by Rohit Pradhan |
Java
/*package whatever //do not write package name here */ import java.io.*; import java.util.*; class GFG { // Function to find number of subarrays // with sum equal to 0. public static int CountSubStringsWithZeroSum(ArrayList<Integer> arr) { int n = arr.size(); // Creating default dictionary with default val // zero. It stores the count of previous subarrays // sum from 0 to i for every i in range(0, // curr_index-1) HashMap<Integer, Integer> prevSum = new HashMap<Integer, Integer>(); for ( int i = 0 ; i < n; i++) { prevSum.put(i, 0 ); } int count = 0 ; int currsum = 0 ; for ( int i = 0 ; i < n; i++) { currsum += arr.get(i); if (currsum == 0 ) count += 1 ; if (prevSum.containsKey(currsum) != false ) count += prevSum.get(currsum); if (prevSum.get(currsum) == null ) prevSum.put(currsum, 0 ); prevSum.put(currsum, prevSum.get(currsum) + 1 ); } return count; } // Function to count subarrays with // number of 0's and 1's in ratio of X:Y public static int countSubStringsWith01InRatioXY(String S, int X, int Y) { // First change 0's to -Y 1's to X ArrayList<Integer> arr = new ArrayList<Integer>(); for ( int i = 0 ; i < S.length(); i++) { if (S.charAt(i) == '0' ) arr.add(- 1 * Y); else arr.add(X); } return CountSubStringsWithZeroSum(arr); } public static void main(String[] args) { String S = "010011010100" ; int X = 3 ; int Y = 2 ; // Function Call System.out.println( countSubStringsWith01InRatioXY(S, X, Y)); } } // This code is contributed by akashish__ |
Python3
# Python3 code to implement the approach from collections import defaultdict # Function to find number of subarrays # with sum equal to 0. def CountSubStringsWithZeroSum(arr): n = len (arr) # Creating default dictionary with default val zero. # It stores the count of previous subarrays sum # from 0 to i for every i in range(0, curr_inndex-1) prevSum = defaultdict( lambda : 0 ) count = 0 currsum = 0 for i in range ( 0 , n): currsum + = arr[i] if currsum = = 0 : count + = 1 if currsum in prevSum: count + = prevSum[currsum] prevSum[currsum] + = 1 return count # Function to count subarrays with # number of 0's and 1's in ratio of X:Y def countSubStringsWith01InRatioXY(S, X, Y): # First change 0's to -Y 1's to X arr = [] for i in S: arr.append( - Y if i = = '0' else X) return CountSubStringsWithZeroSum(arr) # Driver code if __name__ = = "__main__" : S = "010011010100" X = 3 Y = 2 # Function Call print (countSubStringsWith01InRatioXY(S, X, Y)) |
C#
using System; using System.Collections.Generic; using System.Linq; public class GFG { // Function to find number of subarrays // with sum equal to 0. public static int CountSubStringsWithZeroSum(List< int > arr) { int n = arr.Count; // Creating default dictionary with default val // zero. It stores the count of previous subarrays // sum from 0 to i for every i in range(0, // curr_index-1) Dictionary< int , int > prevSum = new Dictionary< int , int >(); for ( int i = 0; i < n; i++) { prevSum.Add(i, 0); } int count = 0; int currsum = 0; for ( int i = 0; i < n; i++) { currsum += arr[i]; if (currsum == 0) count += 1; if (prevSum.ContainsKey(currsum)) count += prevSum[currsum]; if (prevSum.ContainsKey(currsum) == false ) prevSum.Add(currsum, 0); prevSum[currsum] += 1; } return count; } // Function to count subarrays with // number of 0's and 1's in ratio of X:Y public static int countSubStringsWith01InRatioXY(String S, int X, int Y) { // First change 0's to -Y 1's to X List< int > arr = new List< int >(); for ( int i = 0; i < S.Length; i++) { if (S[i] == '0' ) arr.Add(-1 * Y); else arr.Add(X); } return CountSubStringsWithZeroSum(arr); } static public void Main() { String S = "010011010100" ; int X = 3; int Y = 2; // Function Call Console.WriteLine( countSubStringsWith01InRatioXY(S, X, Y)); } } // This code is contributed by akashish__ |
Javascript
// JavaScript code to implement the approach // Function to find number of subarrays // with sum equal to 0. function CountSubStringsWithZeroSum(arr) { let n = arr.length; // Creating default dictionary with default val zero. // It stores the count of previous subarrays sum // from 0 to i for every i in range(0, curr_inndex-1) let prevSum = {}; let count = 0; let currsum = 0; for (let i = 0; i < n; i++) { currsum += arr[i]; if (currsum == 0) count += 1; if (prevSum.hasOwnProperty(currsum)) count += prevSum[currsum]; if (prevSum.hasOwnProperty(currsum)) prevSum[currsum] += 1; else prevSum[currsum] = 1; } return count; } // Function to count subarrays with // number of 0's and 1's in ratio of X:Y function countSubStringsWith01InRatioXY(S, X, Y) { // First change 0's to -Y 1's to X let arr = []; for (i of S) { if (i == "0" ) arr.push(-Y); else arr.push(X); } return CountSubStringsWithZeroSum(arr); } // Driver code let S = "010011010100" ; let X = 3; let Y = 2; // Function Call console.log(countSubStringsWith01InRatioXY(S, X, Y)); // This code is contributed by Ishankhandelwals. |
5
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us