Interview Copilot Tabs

You: Can this be solved without using extra space?

Assistant: Yes, you can use the two-pointer technique to solve
this in-place with O(1) space complexity. Instead of creating
a new array, you can swap elements within the original array...

## 💡 Problem Analysis

### Key Observations
- This is a sliding window problem with variable window size
- Need to track unique characters in current window
- Window expands right, contracts left when constraint violated

### Approach
1. Use HashMap to track character frequencies in window
2. Expand window by moving right pointer
3. Contract window from left when we exceed k unique chars
4. Track maximum window size seen

### Edge Cases to Consider
- Empty string → return 0
- k = 0 → return 0
- k ≥ unique chars in string → return string length
- All characters the same → window = entire string

### Complexity Targets
- Time: O(n) - single pass with two pointers
- Space: O(k) - at most k unique characters in HashMap

def lengthOfLongestSubstringKDistinct(s: str, k: int) -> int:
    """
    Find the length of the longest substring with at most k distinct characters.
    
    Time Complexity: O(n)
    Space Complexity: O(k)
    """
    if k == 0 or not s:
        return 0
    
    # Track character frequencies in current window
    char_count = {}
    max_length = 0
    left = 0
    
    for right in range(len(s)):
        # Add character to window
        char_count[s[right]] = char_count.get(s[right], 0) + 1
        
        # Contract window if we exceed k distinct characters
        while len(char_count) > k:
            char_count[s[left]] -= 1
            if char_count[s[left]] == 0:
                del char_count[s[left]]
            left += 1
        
        # Update maximum length
        max_length = max(max_length, right - left + 1)
    
    return max_length

## 🚶 Step-by-Step Walkthrough

### Step 1: Initialization
We set up:
- `char_count`: HashMap to track character frequencies in our window
- `max_length`: Stores the longest valid window we've found
- `left`: Left pointer for sliding window (starts at 0)

### Step 2: Expand Window (Right Pointer)
For each character at position `right`:
- Add it to our window by incrementing count in `char_count`
- This potentially adds a new distinct character

### Step 3: Contract Window (Left Pointer)
When we have more than `k` distinct characters:
- Remove characters from the left until we're back to `k` distinct
- Decrement count for character at `left`
- Remove from HashMap if count reaches 0
- Move `left` pointer forward

### Step 4: Track Maximum
After each expansion/contraction:
- Current window size = `right - left + 1`
- Update `max_length` if this window is larger

### Complexity Analysis

| Metric | Value | Explanation |
|--------|-------|-------------|
| Time   | O(n)  | Each character visited at most twice (right pointer once, left pointer once) |
| Space  | O(k)  | HashMap stores at most k distinct characters |

### Why This Works
The sliding window maintains the invariant: **at most k distinct characters**.
We never need to look back because we're tracking all possibilities as we go.

✓ User prefers Python for technical interviews
  Stored: 2 days ago

✓ User uses descriptive variable names, not abbreviations
  Stored: 1 week ago

✓ User is preparing for FAANG interviews, focuses on medium/hard problems
  Stored: 3 days ago

✓ User struggled with backtracking problems but improving
  Stored: 5 hours ago