Watch 10 video solutions for Take K of Each Character From Left and Right, a medium level problem involving Hash Table, String, Sliding Window. This walkthrough by NeetCodeIO has 16,432 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 either the leftmost character of s, or the rightmost character of s.
Return the minimum number of minutes needed for you to take at least k of each character, or return -1 if it is not possible to take k of each character.
Example 1:
Input: s = "aabaaaacaabc", k = 2 Output: 8 Explanation: Take three characters from the left of s. You now have two 'a' characters, and one 'b' character. Take five characters from the right of s. You now have four 'a' characters, two 'b' characters, and two 'c' characters. A total of 3 + 5 = 8 minutes is needed. It can be proven that 8 is the minimum number of minutes needed.
Example 2:
Input: s = "a", k = 1 Output: -1 Explanation: It is not possible to take one 'b' or 'c' so return -1.
Constraints:
1 <= s.length <= 105s consists of only the letters 'a', 'b', and 'c'.0 <= k <= s.lengthProblem Overview: You are given a string s containing only a, b, and c. Each minute you can remove a character from either the left or the right end. The goal is to take at least k of each character. Return the minimum number of minutes required, or -1 if it's impossible.
Approach 1: Two-Pointer Technique (O(n) time, O(1) space)
Start by counting the total occurrences of a, b, and c. If any count is less than k, the task is impossible. Use two pointers to simulate taking characters from both ends. Move the right pointer from the end of the string while tracking how many characters have been taken. If removing characters from the right satisfies part of the requirement, adjust the left pointer to minimize the total removals. This approach maintains running counts of characters removed from both sides and greedily shrinks the window to keep the number of operations minimal. The algorithm scans the string once, giving O(n) time complexity and constant O(1) extra space.
Approach 2: Sliding Window Complement (Greedy) (O(n) time, O(1) space)
Instead of deciding which characters to remove, focus on the middle substring you keep. If you must take k of each character, the remaining substring can contain at most total[c] - k of each character. Use a sliding window to find the longest valid middle segment whose character frequencies stay within these limits. Expand the right pointer and track counts with a small array or hash table. If any character exceeds its allowed count, move the left pointer until the window becomes valid again. The answer becomes n - longest_window, which represents the minimum characters removed from both ends. This greedy observation converts the problem into a classic string window problem.
Recommended for interviews: The Sliding Window Complement approach is what most interviewers expect. Recognizing that removing from both ends is equivalent to keeping the largest valid middle substring shows strong problem reduction skills. The two-pointer removal simulation demonstrates the same idea from another angle, but the sliding window formulation is cleaner and easier to reason about in O(n) time.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Technique | O(n) | O(1) | Useful when reasoning directly about characters removed from the left and right ends. |
| Sliding Window Complement (Greedy) | O(n) | O(1) | Best general solution. Converts the problem into finding the longest valid substring. |