Smallest window containing 0, 1 and a pair of

Given a string S of dimension N consisting of the characters 0, 1 and a pair of, the duty is to search out the size of the smallest substring of string S that accommodates all of the three characters 0, 1 and a pair of. If no such substring exists, then return -1.

Examples:

Enter: S = “01212”
Output: 3
Clarification: The substring 012 is the smallest substring
that accommodates the characters 0, 1 and a pair of.

Enter:  S = “12121”
Output: -1
Clarification:  Because the character 0 just isn’t current within the
string S, therefor no substring containing
all of the three characters 0, 1 and a pair of
exists. Therefore, the reply is -1 on this case.

Strategy: The concept of the method is as talked about beneath:

Use three tips that could retailer the indices of the weather 0, 1 and a pair of. When all of the three components are discovered, the space between the utmost of them and the minimal of them is the minimal dimension window.
Maintain updating the pointers at any time when any of them is discovered once more and calculate the scale of the brand new window.

Observe the illustration beneath for a greater understanding.

Illustration:

Take into account S = “01212” and th three tips that could be zeroindex, oneindex and twoindex and all of them are -1 initially.

When i = 0:
        => S[i] = ‘0’. zeroindex = 0, oneindex = -1, twoindex = -1
        => All the values are usually not discovered. So no window is feasible

When i = 1:
        => S[i] = ‘1’. zeroindex = 0, oneindex = 1, twoindex = -1
        => All the values are usually not discovered. So no window is feasible

When i = 2:
        => S[i] = ‘2’. zeroindex = 0, oneindex = 1, twoindex = 2
        => All the values are discovered. 
        => Most is twoindex = 2. Minimal is zeroindex = 0.
        => So window dimension = (2 – 0 + 1) = 3.
        => Minimal window dimension = 3

When i = 3:
        => S[i] = ‘1’. zeroindex = 0, oneindex = 3, twoindex = 2
        => All the values are discovered. 
        => Most is oneindex = 3. Minimal is zeroindex = 0.
        => So window dimension = (3 – 0 + 1) = 4.
        => Minimal window dimension = min (3, 4) = 3

When i = 4:
        => S[i] = ‘2’. zeroindex = 0, oneindex = 3, twoindex = 4
        => All the values are discovered. 
        => Most is twoindex = 4. Minimal is zeroindex = 0.
        => So window dimension = (4 – 0 + 1) = 5.
        => Minimal window dimension = min(3, 5) = 3

So the scale of the smallest window is 3

Observe the beneath steps to resolve the issue:

• Take three variable zero, one and two to examine if 0, 1 and a pair of are discovered within the window or not.
• Take three variables zeroindex, oneindex and twoindex which is able to retailer indexes of 0, 1 and a pair of once we encounter them.
• Run the for loop for the entire size of String:
  • Replace the indices of the values encountered.
  • Replace the size of the window, if three of them are discovered.
  • Size would be the distinction between the utmost and the minimal of the indexes of 0, 1 and a pair of.
• And if all three values i.e., 0, 1, 2 are usually not discovered after the traversal is over then in that case return ‘-1’.

Under is the implementation of the above method:

Time Complexity: O(N)
Auxiliary Area: O(1)