⚡Flashcard Drill➔
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

  1. 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 k occurrences remaining outside it.
  2. Equivalently, for a window [l, r], the condition is total[ch] - window_count[ch] >= k for every character.
  3. Slide the window to maximise its length subject to that condition.
  4. The answer is n - (longest such window). If any character occurs fewer than k times 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 k times, the answer is -1.
  • Returning best: the answer is the number of characters taken, which is n - best.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Sliding Window Problems