UWP  

Smallest Window Containing ‘0’, ‘1’, and ‘2’

Problem Summary

You’re given a string s made up of only '0', '1', and '2'.

Your task:
Find the length of the smallest substring that contains all three characters at least once.

If it’s not possible, return -1.

Key Insight

Instead of checking all substrings (which is slow), we use the Sliding Window technique.

Why Sliding Window?

Because:

  • We need a continuous substring

  • We want the smallest valid window

  • We can expand and shrink dynamically

Concept Explained

Think of a window (substring) defined by two pointers:

[left .... right]

Step 1: Expand Window

Move right forward and include characters.

Step 2: Check Validity

If the window contains:

  • at least one '0'

  • at least one '1'

  • at least one '2'

Then it's valid.

Step 3: Shrink Window

Move left forward to minimize the window while keeping it valid.

Example Walkthrough

Input:

s = "10212"

Step-by-step:

  • Step: 1
    Window: "1"
    Contains 0,1,2?: NO
    Action: Expand
    Length: -

  • Step: 2
    Window: "10"
    Contains 0,1,2?: NO
    Action: Expand
    Length: -

  • Step: 3
    Window: "102"
    Contains 0,1,2?: YES
    Action: Update min
    Length: 3

  • Step: 4
    Window: "021"
    Contains 0,1,2?: YES
    Action: Shrink
    Length: 3

  • Step: 5
    Window: "212"
    Contains 0,1,2?: NO
    Action: Expand
    Length: -

Output:

3

Another Example

Input:

s = "12121"

There is no '0' in the string.

Output:

-1

Algorithm

  • Use an array count[3] to track frequency of '0', '1', '2'

  • Use two pointers: left and right

Expand right:

  • Add character to count

If all 3 characters are present:

  • Update minimum length

  • Move left to shrink window

Repeat until end

Code (Java)

class Solution {
    public int smallestSubstring(String s) {
        int n = s.length();
        
        int[] count = new int[3];
        int left = 0, minLen = Integer.MAX_VALUE;
        int unique = 0;

        for (int right = 0; right < n; right++) {
            int idx = s.charAt(right) - '0';

            if (count[idx] == 0) unique++;
            count[idx]++;

            while (unique == 3) {
                minLen = Math.min(minLen, right - left + 1);

                int leftIdx = s.charAt(left) - '0';
                count[leftIdx]--;

                if (count[leftIdx] == 0) unique--;
                left++;
            }
        }

        return minLen == Integer.MAX_VALUE ? -1 : minLen;
    }
}

Complexity

  • Time Complexity: O(n)

    • Each character is processed at most twice

  • Space Complexity: O(1)

    • Only 3 counters used

Key Takeaways

  • This is a classic sliding window problem

Always:

  • Expand → until valid

  • Shrink → to minimize

Works for many problems like:

  • Smallest substring with all characters

  • Longest substring with constraints

Summary

This article explains how to find the smallest substring containing all characters '0', '1', and '2' using a sliding window approach, where the window dynamically expands and shrinks to maintain validity and achieve optimal performance in linear time with constant space.

Membership not found