NeetCode #252LC-2516MediumSliding Window
← Back to All Problems#252 · #2516 · Take K of Each Character From Left and Right(每种字符至少取 K 个)
📌 Problem Statement & Constraints
You are given a string
s consisting of the characters a, b and c, and a non-negative integer k. Each minute you may take one character from either the left or the right end. Return the minimum number of minutes to take at least k of each character, or -1 if impossible. Constraints: 1 <= s.length <= 2 * 10^5, 0 <= k <= s.length.💡 Core Algorithmic Approaches
- Taking from both ends leaves a contiguous middle segment untouched. So the task is to find the longest middle segment that can be left behind, i.e. one where each character still has at least
koccurrences remaining outside it. - Equivalently, for a window
[l, r], the condition istotal[ch] - window_count[ch] >= kfor every character. - Slide the window to maximise its length subject to that condition.
- The answer is
n - (longest such window). If any character occurs fewer thanktimes overall, the answer is -1.
💻 Benchmark Python3 Implementation
class Solution:
def takeCharacters(self, s: str, k: int) -> int:
from collections import Counter
total = Counter(s)
for ch in "abc":
if total[ch] < k:
return -1 # impossible
cnt = Counter()
l = 0
best = 0
for r, ch in enumerate(s):
cnt[ch] += 1
# the window may be removed only if enough remains outside it
while total["a"] - cnt["a"] < k or total["b"] - cnt["b"] < k or total["c"] - cnt["c"] < k:
cnt[s[l]] -= 1
l += 1
best = max(best, r - l + 1)
return len(s) - best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): the window scan is linear.
💾 Space Complexity
O(1): two fixed-size counters.
⚠️ Interview Pitfalls & Follow-ups
- Greedily taking from the ends: the optimal strategy is not greedy -- it corresponds to leaving the longest removable middle segment.
- Checking only the character of the entering element: the condition involves all three characters, so all three must be checked.
- Forgetting the impossibility check: if some character occurs fewer than
ktimes, the answer is -1. - Returning
best: the answer is the number of characters taken, which isn - best.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Sliding Window Problems
#219 · #219Contains Duplicate II#220 · #121Best Time to Buy and Sell Stock#221 · #2379Minimum Recolors to Get K Consecutive Black Blocks#222 · #1984Minimum Difference Between Highest and Lowest of K Scores#223 · #1343Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold#224 · #1052Grumpy Bookstore Owner