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.
This approach utilizes a two-pointer technique to simultaneously check from the left and from the right, aiming to fulfill the requirement of obtaining at least 'k' of each character ('a', 'b', 'c'). The key idea is to keep track of character counts from both ends and to update pointers strategically to achieve the minimum number of moves.
This Python solution first checks if it's possible to form 'k' occurrences of each character by counting their frequencies. The two-pointer approach is implemented to keep track of minimal steps needed by effectively sliding a window approach from both ends of the string. Adjust pointers and update current character counts to determine the smallest window, ensuring minimal moves.
Time Complexity: O(n), where n is the length of the string, as every character is processed at most twice.
Space Complexity: O(1), as the storage requirement does not scale with input size beyond a fixed size.
This approach involves identifying the largest contiguous subarray that lacks at least 'k' of one or more characters. By calculating the complement of such subarrays, we aim to find the minimal total of minutes required.
The Java implementation calculates the shortest segment where all characters meet the conditions less than `k`. The required length is derived from the complement idea and uses a greedy sliding window strategy to find the maximum length of allowable segments, yielding the minimal minutes required for removal.
Java
JavaScript
Time Complexity: O(n), stemming from a single pass to compute with sliding window technique.
Space Complexity: O(1) as the space needed is independent of the input size.
First, we use a hash table or an array of length 3, denoted as cnt, to count the number of each character in string s. If any character appears less than k times, it cannot be obtained, so we return -1 in advance.
The problem asks us to remove characters from the left and right sides of the string, so that the number of each remaining character is not less than k. We can consider the problem in reverse: remove a substring of certain size in the middle, so that in the remaining string on both sides, the number of each character is not less than k.
Therefore, we maintain a sliding window, with pointers j and i representing the left and right boundaries of the window, respectively. The string within the window is what we want to remove. Each time we move the right boundary i, we add the corresponding character s[i] to the window (i.e., remove one character s[i]). If the count of cnt[s[i]] is less than k, then we move the left boundary j in a loop until the count of cnt[s[i]] is not less than k. The size of the window at this time is i - j + 1, and we update the maximum window size.
The final answer is the length of string s minus the size of the maximum window.
The time complexity is O(n), where n is the length of string s. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Two-Pointer Technique | Time Complexity: O(n), where n is the length of the string, as every character is processed at most twice. |
| Sliding Window Complement (Greedy) | Time Complexity: O(n), stemming from a single pass to compute with sliding window technique. |
| Sliding Window | — |
| 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. |
Take K of Each Character From Left and Right - Leetcode - Python • NeetCodeIO • 16,432 views views
Watch 9 more video solutions →Practice Take K of Each Character From Left and Right with our built-in code editor and test cases.
Practice on FleetCode