Smallest window containing 0, 1 and 2

Last Updated : 10 Mar, 2025

Given a string S of size N consisting of the characters 0, 1 and 2, the 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.

Examples:

Input: S = "01212"
Output: 3
Explanation: The substring 012 is the smallest substring that contains the characters 0, 1 and 2.
Input: S = "12121"
Output: -1
Explanation: As the character 0 is not present in the string S, therefore no substring containing all the three characters 0, 1 and 2 exists. Hence, the answer is -1 in this case.

Try it on GfG Practice

Table of Content

[Approach - 1] Index Tracking - O(n) Time and O(1) Space
[Approach - 2] Using a sliding window - O(n) Time and O(1) Space

[Approach - 1] Index Tracking - O(n) Time and O(1) Space

Keep track of the last seen indices of '0', '1', and '2' while iterating through the string. Once all three characters are found, compute the substring length as the difference between the maximum and minimum of the three indices. Update the minimum length found and return the result.

Illustration with Example:

C++

#include <bits/stdc++.h>
using namespace std;

int smallestSubstring(string &S)
{
    int res = INT_MAX;
    
    // To check 0, 1 and 2
    bool zero = false, one = false, two = false;
    
    // To store indexes of 0, 1 and 2
    int zeroindex, oneindex, twoindex;
    for (int i = 0; i < S.length(); i++) {
        if (S[i] == '0') {
            zero = true;
            zeroindex = i;
        }
        else if (S[i] == '1') {
            one = true;
            oneindex = i;
        }
        else if (S[i] == '2') {
            two = true;
            twoindex = i;
        }

        // Calculating length
        if (zero and one and two)
            res = min(res,
                      max({ zeroindex, oneindex, twoindex })
                          - min({ zeroindex, oneindex, twoindex }));
    }

    // In case if there is no substring that contains 0,1 and 2
    if (res == INT_MAX)
        return -1;
    return res + 1;
}

// Driver Code
int main()
{
    string S = "01212";

    // Function call
    cout << smallestSubstring(S);
    return 0;
}

// This code is contributed by Aditya Kumar (adityakumar129)

C

// C program for above approach

#include <limits.h> // to use INT_MAX
#include <stdbool.h> //to use bool variable
#include <stdio.h>

// function to calculate max of two numbers
int min_two(int a, int b)
{
    if (a <= b)
        return a;
    else
        return b;
}

// function to calculate max of three numbers
int max_three(int a, int b, int c)
{
    if (a >= b && a >= c)
        return a;
    else if (b > a && b >= c)
        return b;
    else if (c > a && c > b)
        return c;
}

// function to calculate min of three numbers
int min_three(int a, int b, int c)
{
    if (a <= b && a <= c)
        return a;
    else if (b < a && b <= c)
        return b;
    else if (c < a && c < b)
        return c;
}

// Function to find the length of
// the smallest substring
int smallestSubstring(char S[])
{
    int res = INT_MAX;
    int n = strlen(S);
    // To check 0, 1 and 2
    bool zero = 0, one = 0, two = 0;

    // To store indexes of 0, 1 and 2
    int zeroindex, oneindex, twoindex;
    for (int i = 0; i < n; i++) {
        if (S[i] == '0') {
            zero = true;
            zeroindex = i;
        }
        else if (S[i] == '1') {
            one = true;
            oneindex = i;
        }
        else if (S[i] == '2') {
            two = true;
            twoindex = i;
        }

        // Calculating length
        if (zero && one && two)
            res = min_two( res,
                     max_three(zeroindex, oneindex, twoindex)
                    - min_three(zeroindex, oneindex, twoindex));
    }

    // In case if there is no substring that contains 0,1 and 2
    if (res == INT_MAX)
        return -1;
    return res + 1;
}

// Driver Code
int main()
{
    char S[] = "01212";

    int ans = smallestSubstring(S);
    // Function call
    printf("%d", ans);
    return 0;
}

// This code is contributed by Aditya Kumar (adityakumar129)

Java

// Java program for above approach
import java.util.*;
class GfG {

    // Function to find the length of the smallest substring
    public static int smallestSubstring(String S)
    {
        int res = Integer.MAX_VALUE;

        // To check 0, 1 and 2
        boolean zero = false, one = false, two = false;

        // To store indexes of 0, 1 and 2
        int zeroindex = 0, oneindex = 0, twoindex = 0;
        for (int i = 0; i < S.length(); i++) {
            if (S.charAt(i) == '0') {
                zero = true;
                zeroindex = i;
            }
            else if (S.charAt(i) == '1') {
                one = true;
                oneindex = i;
            }
            else if (S.charAt(i) == '2') {
                two = true;
                twoindex = i;
            }

            // Calculating length
            if (zero && one && two)
                res = Math.min( res,
                    Math.max(zeroindex,Math.max(oneindex, twoindex))
                  - Math.min( zeroindex,Math.min(oneindex, twoindex)));
        }

        // In case if there is no substring that contains 0,1 and 2
        if (res == Integer.MAX_VALUE)
            return -1;
        return res + 1;
    }

    // Driver Code
    public static void main(String[] args)
    {
        String S = "01212";
        // Function call
        System.out.print(smallestSubstring(S));
    }
}

Python

def smallestSubstring(S):
    res = 999999

    # To check 0, 1 and 2
    zero = 0
    one = 0
    two = 0

    zeroindex = 0
    oneindex = 0
    twoindex = 0
    for i in range(len(S)):
        if (S[i] == '0'):
            zero = 1
            zeroindex = i

        elif (S[i] == '1'):
            one = 1
            oneindex = i

        elif (S[i] == '2'):
            two = 1
            twoindex = i

        # Calculating length
        if (zero and one and two):
            res = min(res,
                      max([zeroindex, oneindex, twoindex])
                      - min([zeroindex, oneindex, twoindex]))

    if (res == 999999):
        return -1
    return res + 1


# Driver Code
S = "01212"

# Function call
print(smallestSubstring(S))

C#

// C# program for above approach
using System;

public class GfG {

    // Function to find the length of the smallest substring
    static int smallestSubstring(string S)
    {
        int res = Int32.MaxValue;

        // To check 0, 1 and 2
        bool zero = false, one = false, two = false;

        // To store indexes of 0, 1 and 2
        int zeroindex = 0, oneindex = 0, twoindex = 0;
        for (int i = 0; i < S.Length; i++) {
            if (S[i] == '0') {
                zero = true;
                zeroindex = i;
            }
            else if (S[i] == '1') {
                one = true;
                oneindex = i;
            }
            else if (S[i] == '2') {
                two = true;
                twoindex = i;
            }

            // Calculating length
            if (zero && one && two)
                res = Math.Min(res,
                    Math.Max( zeroindex, Math.Max(oneindex, twoindex))
                  - Math.Min( zeroindex, Math.Min(oneindex, twoindex)));
        }

        // In case if there is no substring that contains 0,1 and 2
        if (res == Int32.MaxValue)
            return -1;
        return res + 1;
    }

    // Driver Code
    static public void Main()
    {
        string S = "01212";

        // Function call
        Console.Write(smallestSubstring(S));
    }
}

JavaScript

const smallestSubstring = (S) => {
            let res = 9999999;

            // To check 0, 1 and 2
            let zero = false, one = false, two = false;

            // To store indexes of 0, 1 and 2
            let zeroindex, oneindex, twoindex;
            for (let i = 0; i < S.length; i++) {
                if (S[i] == "0") {
                    zero = true;
                    zeroindex = i;
                }
                else if (S[i] == "1") {
                    one = true;
                    oneindex = i;
                }
                else if (S[i] == "2") {
                    two = true;
                    twoindex = i;
                }

                // Calculating length
                if (zero && one && two)
                    res = Math.min(res,
                        Math.max(...[zeroindex, oneindex, twoindex])
                      - Math.min(...[zeroindex, oneindex, twoindex]));
            }

            // In case if there is no substring that contains 0,1 and 2
            if (res == 9999999)
                return -1;
            return res + 1;
        }

        // Driver Code
        let S = "01212";

// Function call
console.log(smallestSubstring(S));

Output

[Approach - 2] Using a sliding window - O(n) Time and O(1) Space

Use two pointers (i and k) and a frequency array to track the count of '0', '1', and '2'. Expand the window by moving k, and when all three characters are present, shrink it from the left (i) to maintain the smallest valid substring. Return the minimum length found.

C++

#include <bits/stdc++.h>
using namespace std;

int smallestSubstring(string &S) {
    int n = S.length(), i = 0, j = 0, k = 0, cnt = 0, min_len = INT_MAX;
    int freq[3] = {0};
    while (k < n) {
        freq[S[k]-'0']++;
        if (freq[S[k]-'0'] == 1) cnt++;
        if (cnt == 3) {
            while (freq[S[i]-'0'] > 1) {
                freq[S[i]-'0']--;
                i++;
            }
            min_len = min(min_len, k-i+1);
            freq[S[i]-'0']--;
            i++;
            cnt--;
        }
        k++;
    }
    return (min_len == INT_MAX) ? -1 : min_len;
}

int main() {
    string S = "01212";
    cout << smallestSubstring(S) << endl;
    return 0;
}

Java

import java.util.Arrays;

class GfG {

    static int smallestSubstring(String S)
    {
        int n = S.length(), i = 0, j = 0, k = 0, cnt = 0,
            min_len = Integer.MAX_VALUE;
        int[] freq = new int[3];
        Arrays.fill(freq, 0);
        while (k < n) {
            freq[S.charAt(k) - '0']++;
            if (freq[S.charAt(k) - '0'] == 1)
                cnt++;
            if (cnt == 3) {
                while (freq[S.charAt(i) - '0'] > 1) {
                    freq[S.charAt(i) - '0']--;
                    i++;
                }
                min_len = Math.min(min_len, k - i + 1);
                freq[S.charAt(i) - '0']--;
                i++;
                cnt--;
            }
            k++;
        }
        return (min_len == Integer.MAX_VALUE) ? -1
                                              : min_len;
    }

    public static void main(String[] args)
    {
        String S = "01212";
        System.out.println(smallestSubstring(S));
    }
}

Python

def smallestSubstring(S):

    # Initialize variables
    n, i, j, k, cnt, min_len = len(S), 0, 0, 0, 0, float("inf")

    # Frequency array
    freq = [0] * 3

    while k < n:
        freq[int(S[k])] += 1
        if freq[int(S[k])] == 1:
            cnt += 1

        if cnt == 3:
            while freq[int(S[i])] > 1:
                freq[int(S[i])] -= 1
                i += 1
            min_len = min(min_len, k - i + 1)
            freq[int(S[i])] -= 1
            i += 1
            cnt -= 1
        k += 1

    return -1 if min_len == float("inf") else min_len


# Driver code
S = "01212"

print(smallestSubstring(S))

C#

using System;

class GfG {
    static int SmallestSubstring(string s)
    {
        int n = s.Length, i = 0, k = 0, cnt = 0,
            min_len = int.MaxValue;
        int[] freq = new int[3];
        Array.Fill(freq, 0);

        while (k < n) {
            freq[s[k] - '0']++;
            if (freq[s[k] - '0'] == 1)
                cnt++;
            if (cnt == 3) {
                while (freq[s[i] - '0'] > 1) {
                    freq[s[i] - '0']--;
                    i++;
                }
                min_len = Math.Min(min_len, k - i + 1);
                freq[s[i] - '0']--;
                i++;
                cnt--;
            }
            k++;
        }
        return (min_len == int.MaxValue) ? -1 : min_len;
    }

    public static void Main(string[] args)
    {
        string s = "01212";
        Console.WriteLine(SmallestSubstring(s));
    }
}

JavaScript

function smallestSubstring(S)
{
    let n = S.length, i = 0, j = 0, k = 0, cnt = 0,
        min_len = Infinity;

    let freq = [ 0, 0, 0 ];

    while (k < n) {
        freq[parseInt(S[k])] += 1;
        if (freq[parseInt(S[k])] == 1) {
            cnt += 1;
        }

        if (cnt == 3) {
            while (freq[parseInt(S[i])] > 1) {
                freq[parseInt(S[i])] -= 1;
                i += 1;
            }
            min_len = Math.min(min_len, k - i + 1);
            freq[parseInt(S[i])] -= 1;
            i += 1;
            cnt -= 1;
        }
        k += 1;
    }

    return min_len == Infinity ? -1 : min_len;
}

// Driver code
let S = "01212";

// Function call
console.log(smallestSubstring(S));

Output

Comment

Article Tags:

Explore

DSA Fundamentals

Data Structures

Algorithms

Advanced

Interview Preparation

Practice Problem