Coding Problem 4: Smallest window containing 0, 1 and 2 [GFG - Problem Solving]

 Given a string S consisting of the characters 0, 1 and 2. Your task is to find the length of the smallest substring of string S that contains all the three characters 0, 1 and 2. If no such substring exists, then return -1.

Example 1:

Input:
S = 10212
Output:
3
Explanation:
The substring 102 is the smallest substring
that contains the characters 0, 1 and 2.

Example 2:

Input: 
S = 12121
Output:
-1
Explanation: 
As the character 0 is not present in the
string S, therefor no substring containing
all the three characters 0, 1 and 2
exists. Hence, the answer is -1 in this case.

Your Task:
Complete the function smallestSubstring() which takes the string S as input, and returns the length of the smallest substring of string S that contains all the three characters 0, 1 and 2.

Expected Time Complexity: O( length( S ) )
Expected Auxiliary Space: O(1)

Constraints:
1 ≤ length( S ) ≤ 105
All the characters of String S lies in the set {'0', '1', '2'}

Solution : 

Repository: coding-problems: https://lnkd.in/dP5vmnaS

Steps : 

• Take three variables zeroIndex, OneIndex, twoindex, and update the current index number if value match with 0, 1, 2 respectively.
• at the any point if all the variables have some value then calculate the length and update the ans variable according.
  ans =  min(ans, (currentIndex + 1 - min(zeroIndex, oneIndex, twoIndex)
• keep doing it at the end
• check the ans value and return -1 if ans value is not changed. 

package com.coding.problems.gfg;

// User function Template for Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Solution {
    public int smallestSubstring(String S) {
        // Code here
        int zeroIndex = -1;
        int oneIndex = -1;
        int twoIndex = -1;
        int ans = Integer.MAX_VALUE;

        for(int i=0;i< S.length(); i++){
            if(S.charAt(i) == '0'){
                zeroIndex = i;
            }

            if(S.charAt(i) == '1'){
                oneIndex = i;
            }

            if(S.charAt(i) == '2'){
                twoIndex = i;
            }

            if(zeroIndex != -1 && oneIndex != -1 && twoIndex != -1){
                ans = Math.min(ans, (i + 1) - Math.min(zeroIndex, Math.min(oneIndex, twoIndex)));
            }
        }
        if(ans == Integer.MAX_VALUE){
            return  -1;
        }
        return ans;
    }
}
public class SmallestWindow {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int t= Integer.parseInt(reader.readLine());
        while(t-->0){
            String s = reader.readLine();
            Solution solution = new Solution();
            int ans = solution.smallestSubstring(s);
            System.out.println(ans);
        }

    }
}