Cosmic Module

Qubits of DPK

March 15, 2026

Core DSA

1️⃣ LC #3 — Longest Substring Without Repeating Characters

(Also appears in Pattern 2 Hard — see that page for full details)

Core Idea

Sliding window with HashSet. Expand right always. When duplicate, shrink from left.

Optimized → O(n) Time | O(min(n,alphabet)) Space:

java

QUBITS OF DPK

1class Solution {
2    public int lengthOfLongestSubstring(String s) {
3        HashSet<Character> window = new HashSet<>();
4        int left = 0, maxLen = 0;
5        for (int right = 0; right < s.length(); right++) {
6            while (window.contains(s.charAt(right))) {
7                window.remove(s.charAt(left++));
8            }
9            window.add(s.charAt(right));
10            maxLen = Math.max(maxLen, right - left + 1);
11        }
12        return maxLen;
13    }
14}

Dry Run

Input: s = "abcabcbb"

Output: 3

Key Tricks

Window = right - left + 1
Shrink until duplicate removed, then add new char
HashMap optimization: jump left directly to lastSeen + 1

30-Second Interview Explanation

Sliding window. Expand right always. When duplicate found in window, shrink from left until removed. Track max window size. Time O(n), Space O(alphabet).

️ Interview Traps

Off-by-one: right - left + 1 not right - left

Most Common Follow-ups

Q1: Optimize shrinking with HashMap?

java

QUBITS OF DPK

1HashMap<Character, Integer> lastSeen = new HashMap<>();
2int left = 0, maxLen = 0;
3for (int right = 0; right < s.length(); right++) {
4    char c = s.charAt(right);
5    if (lastSeen.containsKey(c) && lastSeen.get(c) >= left)
6        left = lastSeen.get(c) + 1;
7    lastSeen.put(c, right);
8    maxLen = Math.max(maxLen, right - left + 1);
9}

Jump left directly, avoiding repeated shrinking. Still O(n).

2️⃣ LC #424 — Longest Repeating Character Replacement

Core Idea

Sliding window. Window is valid if (windowSize - maxFreq) <= k. Expand right, shrink when invalid.

Optimized → O(n) Time | O(1) Space:

java

QUBITS OF DPK

1class Solution {
2    public int characterReplacement(String s, int k) {
3        int[] freq = new int[26];
4        int left = 0, maxFreq = 0, maxLen = 0;
5        for (int right = 0; right < s.length(); right++) {
6            freq[s.charAt(right) - 'A']++;
7            maxFreq = Math.max(maxFreq, freq[s.charAt(right) - 'A']);
8            while ((right - left + 1) - maxFreq > k) {
9                freq[s.charAt(left) - 'A']--;
10                left++;
11            }
12            maxLen = Math.max(maxLen, right - left + 1);
13        }
14        return maxLen;
15    }
16}

Dry Run

Input: s = "AABABBA", k=1

Output: 4

Key Tricks

Valid window: windowSize - maxFreq <= k (non-dominant chars <= replacements)
maxFreq never decreases — only matters if larger window is valid
Don't recompute maxFreq when shrinking — stale maxFreq is fine

30-Second Interview Explanation

Window valid when (size - mostFreqChar) <= k. Expand right. When window needs more than k replacements, shrink left. Track max valid window. Time O(n), Space O(1).

️ Interview Traps

Recomputing maxFreq during shrink — unnecessary and makes it O(26n)
Not understanding why stale maxFreq is correct: we only care if a LARGER window becomes valid

Most Common Follow-ups

Q1: Why can maxFreq be stale (not updated when shrinking)?

We only care about finding windows LARGER than our current max. A stale maxFreq means we might reject windows we'd accept, but we'd never accept a window smaller than our current answer. The answer only updates when a genuinely better window is found.

3️⃣ LC #209 — Minimum Size Subarray Sum

Core Idea

Variable window. Expand right. When sum >= target, shrink left to minimize length.

Optimized → O(n) Time | O(1) Space:

java

QUBITS OF DPK

1class Solution {
2    public int minSubArrayLen(int target, int[] nums) {
3        int left = 0, windowSum = 0, minLen = Integer.MAX_VALUE;
4        for (int right = 0; right < nums.length; right++) {
5            windowSum += nums[right];
6            while (windowSum >= target) {
7                minLen = Math.min(minLen, right - left + 1);
8                windowSum -= nums[left++];
9            }
10        }
11        return minLen == Integer.MAX_VALUE ? 0 : minLen;
12    }
13}

Dry Run

Input: target=7, nums=[2,3,1,2,4,3]

Output: 2 (subarray [4,3])

Key Tricks

Expand right always, shrink left when sum >= target
Track minimum length INSIDE the while loop (while still valid)
Return 0 if no valid subarray found

30-Second Interview Explanation

Variable sliding window. Expand right. When sum reaches target, record length and shrink from left until invalid again. Track minimum. Time O(n), Space O(1).

️ Interview Traps

Recording length AFTER shrinking — misses the valid state
Not returning 0 for no valid subarray

Most Common Follow-ups

Q1: If array has negatives, does sliding window still work?

No — negative numbers break monotonicity. Use prefix sum + binary search for O(n log n) solution.