DSA 450 Notes

Problem Statement

Given a string, find the smallest window (substring) that contains all the distinct characters of the given string.

Example:

Input: "aabcbcdbca"
Output: "dbca"
Explanation: The string has 4 distinct characters: a, b, c, d. "dbca" is the smallest window containing all of them.

Example 2:

Input: "aaab"
Output: "ab"
Explanation: Distinct characters are 'a' and 'b'. Smallest window is "ab".

Approach 1: Brute Force (Check All Substrings)

Intuition

Generate all substrings, check if each contains all distinct characters, and track the smallest valid one.

Algorithm

Find all distinct characters in the string
For each starting position i
For each ending position j >= i
Check if substring contains all distinct characters
Track minimum length valid substring

java

import java.util.*;

public class Solution {
    public String smallestWindow(String s) {
        int n = s.length();
        
        // Find all distinct characters
        Set<Character> distinctSet = new HashSet<>();
        for (char c : s.toCharArray()) {
            distinctSet.add(c);
        }
        int distinctCount = distinctSet.size();
        
        String result = s;  // Worst case: entire string
        
        for (int i = 0; i < n; i++) {
            Set<Character> windowSet = new HashSet<>();
            for (int j = i; j < n; j++) {
                windowSet.add(s.charAt(j));
                
                // Check if window contains all distinct characters
                if (windowSet.size() == distinctCount) {
                    if (j - i + 1 < result.length()) {
                        result = s.substring(i, j + 1);
                    }
                    break;
                }
            }
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n²) to O(n³) - Checking all substrings
Space Complexity: O(n) - For storing distinct characters

Approach 2: Sliding Window (Optimal)

Intuition

Use a sliding window with two pointers. Expand the right pointer to include all distinct characters, then shrink the left pointer to find the minimum window.

Algorithm

Find count of distinct characters
Expand right pointer until window contains all distinct chars
Shrink left pointer while maintaining all distinct chars
Track minimum window size
Continue until right pointer reaches end

java

import java.util.*;

public class Solution {
    public String smallestWindow(String s) {
        int n = s.length();
        
        // Find all distinct characters
        Set<Character> distinctSet = new HashSet<>();
        for (char c : s.toCharArray()) {
            distinctSet.add(c);
        }
        int distinctCount = distinctSet.size();
        
        // Sliding window
        Map<Character, Integer> windowCount = new HashMap<>();
        int left = 0, right = 0;
        int formed = 0;
        
        int minLen = Integer.MAX_VALUE;
        int minStart = 0;
        
        while (right < n) {
            // Add character from right
            char c = s.charAt(right);
            windowCount.put(c, windowCount.getOrDefault(c, 0) + 1);
            
            if (windowCount.get(c) == 1) {
                formed++;
            }
            
            // Try to shrink window from left
            while (formed == distinctCount) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    minStart = left;
                }
                
                char leftChar = s.charAt(left);
                windowCount.put(leftChar, windowCount.get(leftChar) - 1);
                if (windowCount.get(leftChar) == 0) {
                    formed--;
                }
                left++;
            }
            
            right++;
        }
        
        return (minLen == Integer.MAX_VALUE) ? "" : s.substring(minStart, minStart + minLen);
    }
}

Dry Run Example

Input: "aabcbcdbca"
Distinct characters: {a, b, c, d} = 4

right=0: 'a', window={a:1}, formed=1
right=1: 'a', window={a:2}, formed=1
right=2: 'b', window={a:2,b:1}, formed=2
right=3: 'c', window={a:2,b:1,c:1}, formed=3
right=4: 'b', window={a:2,b:2,c:1}, formed=3
right=5: 'c', window={a:2,b:2,c:2}, formed=3
right=6: 'd', window={a:2,b:2,c:2,d:1}, formed=4 ✓
  → Shrink: left=0, remove 'a', window={a:1,b:2,c:2,d:1}, formed=4
    → min="aabcbcdb", len=8
  → Shrink: left=1, remove 'a', window={a:0,b:2,c:2,d:1}, formed=3
  → Stop shrinking
right=7: 'b', window={a:0,b:3,c:2,d:1}, formed=3
right=8: 'c', window={a:0,b:3,c:3,d:1}, formed=3
right=9: 'a', window={a:1,b:3,c:3,d:1}, formed=4 ✓
  → Shrink: left=2, remove 'b', window={a:1,b:2,c:3,d:1}, formed=4
    → min="bcbcdbca", len=8
  → Shrink: left=3, remove 'c', window={a:1,b:2,c:2,d:1}, formed=4
    → min="cbcdbca", len=7
  → Shrink: left=4, remove 'b', window={a:1,b:1,c:2,d:1}, formed=4
    → min="bcdbca", len=6
  → Shrink: left=5, remove 'c', window={a:1,b:1,c:1,d:1}, formed=4
    → min="cdbca", len=5
  → Shrink: left=6, remove 'd', window={a:1,b:1,c:1,d:0}, formed=3
  → Stop shrinking

Final min="dbca" (positions 6-9), len=4

Complexity Analysis

Time Complexity: O(n) - Each character visited at most twice (once by right, once by left)
Space Complexity: O(k) where k is the number of distinct characters (at most 26 for lowercase)

Key Takeaways

Sliding window is the key technique for substring problems
Two pointers - expand right to satisfy condition, shrink left to minimize
Track "formed" count instead of comparing sets each time
This is a variation of "Minimum Window Substring" problem
Time complexity of O(n) is achieved because each character is processed at most twice
The answer always exists (worst case: entire string)

Write a program to find the smallest window that contains all characters of string itself

Problem Statement

Approach 1: Brute Force (Check All Substrings)

Intuition

Algorithm

Complexity Analysis

Approach 2: Sliding Window (Optimal)

Intuition

Algorithm

Dry Run Example

Complexity Analysis

Key Takeaways