Smallest window containing 0, 1 and 2

Time: O(n)

Space: O(1)

Intuition

We need the shortest substring that contains all three required characters. This is a classic minimum-window pattern: expand right pointer to satisfy the condition, then shrink left pointer as much as possible while still valid. Because each pointer only moves forward, total work is linear.

Algorithm

1Initialize two pointers i=0 and j=0, plus counters for 0/1/2.
2Move j forward; update the counter for s[j].
3Whenever all three counters are at least 1, update answer with current window length.
4Then move i forward to shrink window, decrementing counter for s[i], until condition breaks.
5Continue until j reaches end. If answer was never updated, return -1; otherwise return minimum length.

Example Walkthrough

Input: s = "10212"

1.j=0..2 gives window "102" with counts (1,1,1), answer=3.
2.Try shrinking from left: removing 1 breaks condition, so stop shrinking.
3.Continue expanding; windows "021" and "212" also checked.
4.Minimum valid window length remains 3.

Output: 3

Common Pitfalls

•Do not stop after first valid window; keep shrinking to get the minimum.
•Remember to decrement counts while moving left pointer.
•Return -1 when any required character never appears in the string.

Smallest window containing 0, 1 and 2.java

Java


class Solution {

    // Approach: Sliding window with counts of '0', '1', and '2'; expand right,
    // and shrink left greedily while all three are present.
    // Time: O(n) Space: O(1)

    public int smallestSubstring(String s) {
        int cnt_0 = 0;
        int cnt_1 = 0;
        int cnt_2 = 0;

        int i = 0;
        int j = 0;

        int n = s.length();
        int ans = Integer.MAX_VALUE;

        while (j < n) {
            char ch_At_j = s.charAt(j);
            if (ch_At_j == '0') {
                cnt_0++;
            }
            if (ch_At_j == '1') {
                cnt_1++;
            }
            if (ch_At_j == '2') {
                cnt_2++;
            }

            while (cnt_0 >= 1 && cnt_1 >= 1 && cnt_2 >= 1) {
                ans = Math.min(ans, j - i + 1);
                char ch_At_i = s.charAt(i);
                if (ch_At_i == '0') {
                    cnt_0--;
                }
                if (ch_At_i == '1') {
                    cnt_1--;
                }
                if (ch_At_i == '2') {
                    cnt_2--;
                }
                i++;
            }
            j++;
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
};

Was this solution helpful?