Test if any round rotation of String has at most X 1s between two adjoining 0s

Given a binary string S of size N and an integer X, the duty is to verify if there exists a right-wise round rotation of the string such that each 2 adjoining 0′s are separated by at most X 1′s.

Be aware: The primary and the final 0s within the string aren’t thought-about to be adjoining 

Examples:

Enter: S = “010110”, X = 1        
Output: Sure 

Clarification: The 6 round rotations of the string 
S = {“010110”, “001011”, “100101”, “110010”, “011001”, “101100”} 
out of which second , third and fourth strings fulfill the factors.
Therefore there exist a binary string which fulfill above situation.

Enter:  S = “0101”, X = 0

Output: No

Strategy: The issue may be solved based mostly on the next remark: 

Assuming the final character to be adjoining to first, we will discover the variety of ones between every pair of adjoining ones in an inventory. Now, the rotation of binary string is equal to deleting at most one ingredient of this record. So if remainder of the weather are as much as X, then the reply is YES.

Observe the beneath steps to implement the above concept:

• Discover the positions of all 0’s within the array.
• Discover the variety of 1s between any two adjoining 0s.
• If there may be at most 1 such section of contiguous 1s having size X or extra then that section may be partitioned to be within the begin or final. So print “Sure”;
• In any other case, it prints “No”.

Beneath is the implementation of the above strategy.

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