DSA 450 Notes

Problem Statement

Given two strings s and t, find the smallest window (substring) in s that contains all characters of t (including duplicates).

Example:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: "BANC" is the smallest substring of s containing A, B, and C

Example 2:

Input: s = "a", t = "a"
Output: "a"

Approach 1: Brute Force (Check All Substrings)

Intuition

Generate all substrings of s and check if each contains all characters of t. Track the smallest valid one.

Algorithm

Create frequency map of t
For each starting position i in s
For each ending position j >= i
Check if substring s[i..j] contains all characters of t
Track minimum length valid substring

java

import java.util.*;

public class Solution {
    private boolean containsAll(String s, int start, int end, Map<Character, Integer> tCount) {
        Map<Character, Integer> windowCount = new HashMap<>();
        for (int i = start; i <= end; i++) {
            char c = s.charAt(i);
            windowCount.put(c, windowCount.getOrDefault(c, 0) + 1);
        }
        
        for (Map.Entry<Character, Integer> e : tCount.entrySet()) {
            if (windowCount.getOrDefault(e.getKey(), 0) < e.getValue()) {
                return false;
            }
        }
        return true;
    }
    
    public String minWindow(String s, String t) {
        int n = s.length(), m = t.length();
        if (n < m) return "";
        
        Map<Character, Integer> tCount = new HashMap<>();
        for (char c : t.toCharArray()) {
            tCount.put(c, tCount.getOrDefault(c, 0) + 1);
        }
        
        String result = "";
        int minLen = Integer.MAX_VALUE;
        
        for (int i = 0; i < n; i++) {
            for (int j = i + m - 1; j < n; j++) {
                if (containsAll(s, i, j, tCount)) {
                    if (j - i + 1 < minLen) {
                        minLen = j - i + 1;
                        result = s.substring(i, j + 1);
                    }
                    break;
                }
            }
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n³) or O(n² * m) - For each substring, checking takes O(n) or O(m)
Space Complexity: O(m) - For storing character counts

Approach 2: Sliding Window (Optimal)

Intuition

Use two pointers to maintain a sliding window. Expand the right pointer to include all required characters, then shrink from the left to minimize the window.

Algorithm

Create frequency map of t
Use two pointers: left and right
Expand right until window contains all characters of t
Shrink left while maintaining all required characters
Track minimum window found
Repeat until right reaches end

java

import java.util.*;

public class Solution {
    public String minWindow(String s, String t) {
        int n = s.length(), m = t.length();
        if (n < m) return "";
        
        Map<Character, Integer> tCount = new HashMap<>();
        for (char c : t.toCharArray()) {
            tCount.put(c, tCount.getOrDefault(c, 0) + 1);
        }
        
        int required = tCount.size();
        int formed = 0;
        
        Map<Character, Integer> windowCount = new HashMap<>();
        int left = 0, right = 0;
        
        int minLen = Integer.MAX_VALUE;
        int minStart = 0;
        
        while (right < n) {
            char c = s.charAt(right);
            windowCount.put(c, windowCount.getOrDefault(c, 0) + 1);
            
            if (tCount.containsKey(c) && 
                windowCount.get(c).intValue() == tCount.get(c).intValue()) {
                formed++;
            }
            
            while (left <= right && formed == required) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    minStart = left;
                }
                
                char leftChar = s.charAt(left);
                windowCount.put(leftChar, windowCount.get(leftChar) - 1);
                if (tCount.containsKey(leftChar) && 
                    windowCount.get(leftChar) < tCount.get(leftChar)) {
                    formed--;
                }
                left++;
            }
            
            right++;
        }
        
        return (minLen == Integer.MAX_VALUE) ? "" : s.substring(minStart, minStart + minLen);
    }
}

Dry Run Example

s = "ADOBECODEBANC", t = "ABC"
tCount = {A:1, B:1, C:1}, required = 3

right=0: 'A', window={A:1}, formed=1
right=1: 'D', window={A:1,D:1}, formed=1
right=2: 'O', window={A:1,D:1,O:1}, formed=1
right=3: 'B', window={A:1,D:1,O:1,B:1}, formed=2
right=4: 'E', window={...}, formed=2
right=5: 'C', window={A:1,D:1,O:1,B:1,E:1,C:1}, formed=3 ✓
  → Shrink: left=0, remove A, window={A:0,...}, formed=2
  → minLen=6, minStart=0, result="ADOBEC"
  → Stop shrinking

right=6-9: Add O,D,E,B (formed stays 2, then becomes 3 at B)
right=9: 'B', formed=3 ✓
  → Shrink: ...eventually find "BECODEBA"

right=10: 'A', formed=3 ✓
  → Shrink from left, find "CODEBA", then "ODEBA", etc.
  → Eventually: "BANC" (len=4)

right=11: 'N'
right=12: 'C'
  → Keep shrinking, but "BANC" remains minimum

Output: "BANC"

Complexity Analysis

Time Complexity: O(n + m) - Each character visited at most twice
Space Complexity: O(m) - For storing character counts

Key Takeaways

Sliding window is the key technique for substring problems
Two types of counts: required (unique chars in t) and formed (satisfied in window)
Expand right to satisfy, shrink left to minimize
This is LeetCode 76 - a classic hard problem
Similar problems: Minimum Window Subsequence, Substring with Concatenation of All Words
The formed == required check is more efficient than comparing entire maps

Find the smallest window in a string containing all characters of another string

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