Take K of Each Character From Left and Right — Complement Window (LC 2516)

Problem Statement#

LeetCode 2516 — Take K of Each Character From Left and Right (Medium)

You are given a string s of characters 'a', 'b', 'c' and a non-negative integer k. Each minute you take either the leftmost or rightmost character. Return the minimum number of minutes to take at least k of each character. Return -1 if impossible.

Constraints:

• 1 <= s.length <= 10^5
• s consists only of 'a', 'b', 'c'
• 0 <= k <= s.length

Input:  s = "aabaaaacaabc", k = 2
Output: 8

Input:  s = "a", k = 0
Output: 0

Why This Problem Matters#

LC 2516 showcases the complement window technique. Instead of modeling which characters you take from two separate ends, flip the problem: find the longest middle segment you can skip. The characters you take are everything outside that segment.

This complement thinking appears frequently in senior-level interviews at Google and Meta. It transforms a two-ended collection problem into a classic shrinkable sliding window. The same inversion solves LC 1234 (Replace the Substring for Balanced String) and several other "constraint on the outside" problems. Recognizing when to take the complement is a hallmark of experienced algorithmic thinking.

The Core Insight#

You collect s[0..left-1] and s[right+1..n-1] from the two ends. The characters inside window [left, right] are the ones you skip.

For the outside to have >= k of character c, the window can contain at most total[c] - k of character c. Define budget[c] = total[c] - k.

Find the longest window where all three character counts stay within budget. The answer is n - (longest valid window length).

This is a standard shrinkable sliding window: expand right, shrink left when any budget is exceeded, track the longest valid window. If any total[c] < k, return -1 immediately.

Visual Dry Run#

Input: s = "aabaaaacaabc", k = 2, n = 12

Total: a=8, b=2, c=2. Budget: a=6, b=0, c=0

The window can hold at most 6 as, 0 bs, 0 cs — only all-a substrings qualify. The longest such window has length 4 (positions 3-6: "aaaa").

Answer: 12 - 4 = 8

Solution (Optimal)#

from collections import Counter
 
def takeCharacters(s: str, k: int) -> int:
    n = len(s)
    total = Counter(s)
 
    if any(total[c] < k for c in 'abc'):
        return -1
 
    budget = {c: total[c] - k for c in 'abc'}
    window = Counter()
    left = 0
    max_skip = 0
 
    for right in range(n):
        c = s[right]
        window[c] += 1
 
        while window[c] > budget[c]:
            window[s[left]] -= 1
            left += 1
 
        max_skip = max(max_skip, right - left + 1)
 
    return n - max_skip

var takeCharacters = function(s, k) {
    const n = s.length;
    const total = { a: 0, b: 0, c: 0 };
    for (const c of s) total[c]++;
 
    if (total['a'] < k || total['b'] < k || total['c'] < k) return -1;
 
    const budget = {
        a: total['a'] - k,
        b: total['b'] - k,
        c: total['c'] - k,
    };
 
    const window = { a: 0, b: 0, c: 0 };
    let left = 0, maxSkip = 0;
 
    for (let right = 0; right < n; right++) {
        const c = s[right];
        window[c]++;
 
        while (window[c] > budget[c]) {
            window[s[left]]--;
            left++;
        }
 
        maxSkip = Math.max(maxSkip, right - left + 1);
    }
 
    return n - maxSkip;
};

Time: O(n) — right advances n steps; left advances at most n steps total Space: O(1) — fixed-size counters for 3 characters

Common Mistakes#

• Modeling two moving ends directly — tracking character counts from two independently moving pointers is error-prone
• Forgetting total[c] >= k check — if the entire string lacks k of some character, return -1 immediately
• Using window[c] < budget[c] instead of <= budget[c] in validity check — window can hold exactly budget[c] copies
• Confusing what the window represents — the window is what you skip, not what you take; answer is n - window_size
• Shrinking on all characters when only one violated — shrink while the specifically violated character still exceeds its budget

Interview Tips#

• State the complement insight first: "Instead of tracking what I take from both ends, I find the longest middle segment I can skip"
• Explain budget: budget[c] = total[c] - k is the max of character c the skipped window may contain
• If k == 0, every window is valid; max_skip = n; answer = 0 — algorithm handles this without special-casing
• The while shrinks on the current character c — no need to check all three in the while condition

Follow-up Questions#

• k = 0: budget equals total for each character; entire string is valid middle; answer = 0
• Larger alphabet: generalize budget to all required characters; check each in the while condition
• Binary search alternative: binary search on window length L, check any window of size L fits within budget using prefix sums — O(n log n)
• What if you can also take from the middle? Then you take the whole string; the "from ends only" constraint is what makes the complement window work

Key Takeaways#

• When taking from both ends, flip the problem: find the longest middle window you can skip
• Budget for each character inside the window is total[c] - k — the max allowed inside the skipped segment
• Shrinkable window: expand right unconditionally, shrink left while any character exceeds its budget
• Check total[c] >= k for all characters upfront — return -1 if any character is globally insufficient
• Answer is n - max_skip_window_length; time O(n), space O(1)