Smallest distinct window

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Find smallest window containing all distinct characters of the string. Sliding window.

Algorithm

1Count distinct chars total. Sliding window maintaining frequency map.
2Expand right until all distinct chars covered. Shrink left while maintaining coverage. Track minimum window.

Common Pitfalls

•Window must contain all distinct characters of the original string, not just some.

Smallest distinct window.java

Java

// Approach: Sliding window with frequency map. Find minimum window containing all distinct characters of string.
// Time: O(n) Space: O(1)
import java.util.*;

class Solution {
    public int findSubString(String str) {
        // Step 1: Identify all unique characters in the string
        Set<Character> uniqueChars = new HashSet<>();
        for (char c : str.toCharArray())
            uniqueChars.add(c);

        int uniqueCharCount = uniqueChars.size();

        // Step 2: Sliding window technique
        Map<Character, Integer> charCount = new HashMap<>();
        int start = 0, end = 0;
        int minLength = Integer.MAX_VALUE;
        int distinctCount = 0;

        while (end < str.length()) {
            char currentChar = str.charAt(end);
            charCount.put(currentChar, charCount.getOrDefault(currentChar, 0) + 1);

            // If this character's count becomes 1, increment distinctCount
            if (charCount.get(currentChar) == 1)
                distinctCount++;

            // Try to shrink the window if all unique characters are included
            while (distinctCount == uniqueCharCount) {
                // Update the minimum length
                minLength = Math.min(minLength, end - start + 1);

                // Shrink the window from the left
                char startChar = str.charAt(start);
                charCount.put(startChar, charCount.get(startChar) - 1);

                // If the count of startChar becomes 0, decrement distinctCount
                if (charCount.get(startChar) == 0)
                    distinctCount--;

                start++;
            }

            end++;
        }

        return minLength;
    }
}

Was this solution helpful?