Depend Substrings with variety of 0s and 1s in ratio of X : Y

Given a binary string S, the duty is to rely the substrings having the variety of 0s and 1s within the ratio of X : Y

Examples:

Enter: S = “010011010100”, X = 3, Y = 2
Output: 5
Rationalization: The index vary for the 5 substringss are: 
(0, 4), (2, 6), (6, 10), (7, 11), (2, 11)

Enter: S = “10010101”, X = 1, Y = 2
Output: 2

Naive Strategy: 

The Naive strategy for the issue can be to search out all of the substrings and verify whether or not the variety of 0s and 1s are in ratio X : Y utilizing the prefix sum idea.

Time Complexity: O(N²).
Auxiliary House: O(N)

Environment friendly Strategy:

The issue might be solved utilizing this concept:

Create a brand new array the place all of the 0s are -Y and all 1s are X. Now each time 0s : 1s = X : Y, then in new array the sum of rely of 0s and 1s can be c * X * -Y + c * Y * X = 0, the place c is a continuing not equal to 0.

Observe the steps to resolve this drawback utilizing the environment friendly strategy:

• Create a brand new array from the binary string, the place for every 0 within the binary string there may be -Y within the new array and for every 1 there may be X.
• Now discover the variety of subarrays of the brand new array which have the sum of values = 0, utilizing the idea on this article: Variety of subarrays having sum precisely equal to ok
• Return the rely of subarrays obtained.

Beneath is the implementation of this strategy:

Time Complexity: O(N) 
Auxiliary House: O(N)