2516. Take K of Each Character From Left and Right
Problem Description
You are presented with a string s
that contains only the characters 'a', 'b', and 'c', and a non-negative integer k
. The task is to determine the minimum number of minutes required to take at least k
instances of each character from the string. You can only remove one character per minute, and it must be either the first (leftmost) or the last (rightmost) character of the string. If it's not possible to remove enough characters to meet the condition (at least k
of each character), then the function should return -1
.
Intuition
To solve this problem using an efficient approach, we can apply the sliding window technique. The main idea behind the solution is to find the smallest window in the original string, which, when removed, still leaves at least k
instances of each character 'a', 'b', and 'c'. Then, the number of minutes required would be equal to the length of the original string minus the size of this smallest window.
The process of devising this solution includes:
-
Character Counting: Initially, we count the occurrences of each character ('a', 'b', 'c') in the string. If any character does not have at least
k
instances, it's immediately impossible to accomplish the task, and we return-1
. -
Finding the Smallest Window: Next, we iterate through the string to determine the smallest window that can be removed. As we iterate with a pointer
i
, we decrease the count of the current character, reflecting that we've taken one instance of it from either end. We use another pointerj
to represent the start of the window we want to remove. If after removing a character ati
, we find that any character's count is belowk
, we move the pointerj
forward to add characters back to the window, until each character's count is at leastk
again. -
Tracking the Minimum Minutes: After we find such a window where the character counts outside the window are sufficient, we calculate its size and update the minimum number of minutes if this window is smaller than the previous ones found. The maximum size of the window we want to remove is noted.
At the end of the iteration, the length of the string minus the maximum size of the window we plan to remove will give us the minimum number of minutes needed. We return this value.
Learn more about Sliding Window patterns.
Solution Approach
The solution follows a sliding window approach and uses Python's Counter
class from the collections
module to keep track of the frequency of each character in the string s
. This data structure is essential for efficiently updating and querying the count of the letters 'a', 'b', and 'c'.
Algorithm:
-
Initialize the Counter: Create a Counter object to store the occurrences of each character by passing the string
s
to it. -
Check Possibility: Loop through the character counts. If the count of any of 'a', 'b', or 'c' is less than
k
, return-1
since it's impossible to satisfy the condition. -
Initialize Pointers and Answer: Set up two pointers,
i
andj
, to iterate through the string.i
will go from the start to the end of the string, whilej
will mark the beginning of the sliding window. Initializeans
to 0, which will keep track of the maximum window size found that maintains at leastk
occurrences of each character outside the window. -
Iterate and Find Window: Loop through the string using the pointer
i
:- Decrease the count of the character
s[i]
from theCounter
, as removing the characters[i]
from either end means it's no longer part of the string outside the window. - If the count of the current character
c
after decreasing becomes less thank
, it means we need to move the other pointerj
forwards to expand the sliding window and add characters back to the count, until all counts are again at leastk
. - During this adjustment, if
s[j]
is added back to the window, increase its count in theCounter
and movej
forward by 1. - Ensure that through these adjustments, the count of every character outside the window remains at least
k
.
- Decrease the count of the character
-
Calculate Maximum Window: After each iteration, update
ans
with the size of the current window if it is larger than the previousans
. This window represents the maximum size that left at leastk
occurrences of each character outside. -
Result: After completing the loop, the answer will be the total length of the string minus the maximum window size that we can remove while leaving at least
k
occurrences of each character. This gives us the minimum number of minutes needed, which we return.
The solution's effectiveness stems from its O(n)
complexity where n
is the length of the string, since each character is processed at most twice: once when increasing the window size (j
moves forward) and once when decreasing (i
moves forward).
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use the problem approach to solve a small example where we have the string s = "abcbab"
and k = 2
.
-
Initialize the Counter:
- Create a Counter from the string
s
. The Counter will look like this:1{'a': 2, 'b': 3, 'c': 1}
- Create a Counter from the string
-
Check Possibility:
- Since 'c' only has one instance and
k
is 2, it's not possible to have at leastk
instances of 'c' remaining after any removals. Therefore, we immediately return-1
.
- Since 'c' only has one instance and
Now let's consider a different string, s = "abbcabc"
with k = 2
. Starting over with the steps:
-
Initialize the Counter:
- The Counter will look like this:
1{'a': 2, 'b': 3, 'c': 2}
- The Counter will look like this:
-
Check Possibility:
- Every character 'a', 'b', and 'c' occurs at least
k
times, so it's possible to proceed.
- Every character 'a', 'b', and 'c' occurs at least
-
Initialize Pointers and Answer:
i = 0
,j = 0
,ans = 0
(maximum window size to remove is 0 so far).
-
Iterate and Find Window:
-
As we iterate with
i
from 0 to the end of the string, we decrease the count from the Counter when removings[i]
from consideration. -
Here's what happens as
i
progresses:i = 0
: Remove 'a', Counter becomes{'a': 1, 'b': 3, 'c': 2}
. No need to adjustj
, as all counts are still at leastk
.i = 1
: Remove 'b', Counter becomes{'a': 1, 'b': 2, 'c': 2}
. No need to adjustj
, only when a letter goes belowk
do we adjustj
.i = 2
: Remove 'b', Counter becomes{'a': 1, 'b': 1, 'c': 2}
.- Now, removing the next character at
i
will make the count of 'b' go belowk
, so we start movingj
forward to find the maximum window we can remove:j = 0
: Adding 'a' back into the window, Counter becomes{'a': 2, 'b': 1, 'c': 2}
.j = 1
: We cannot movej
forward as it would decrease the count of 'b' which is already at minimum allowed fork
.
By
i = 3
, the count of 'b' can't be allowed to decrease any further without also decreasingj
.
-
-
Calculate Maximum Window:
- The window size with
i = 3
andj = 1
is3 - 1 = 2
. Updateans
to2
.
- The window size with
-
Result:
- Continue iterating with the same strategy till the end. After completing the loop, we find that the maximum window size to remove is
ans = 3
(which happens to be the window "bca" from index 2 to 4). The string length is 7, the answer is7 - 3 = 4
. Thus, it takes a minimum of 4 minutes to remove characters such that at leastk
instances of each remain.
- Continue iterating with the same strategy till the end. After completing the loop, we find that the maximum window size to remove is
The process shows that by using the sliding window method, we managed to find the minimum number of minutes required to remove characters from the string s
while maintaining at least k
instances of each character.
Solution Implementation
1from collections import Counter
2
3class Solution:
4 def takeCharacters(self, s: str, k: int) -> int:
5 # Count the frequency of each character in the string s
6 char_count = Counter(s)
7
8 # Check if the count of any character 'a', 'b', or 'c' is less than k
9 if any(char_count[char] < k for char in "abc"):
10 return -1 # If so, return -1 as we cannot fulfill the requirement
11
12 # Initialize answer and the start index to 0
13 max_length = start_index = 0
14
15 # Iterate over the string with index i and character c
16 for i, c in enumerate(s):
17 char_count[c] -= 1 # Decrement the count of the current character
18
19 # If count of current character is less than k, move the start index forward
20 # to find a valid substring
21 while char_count[c] < k:
22 char_count[s[start_index]] += 1 # Increment the character at start index
23 start_index += 1 # Move the start index forward
24
25 # Update max_length to the maximum length found so far
26 max_length = max(max_length, i - start_index + 1)
27
28 # Return the length of the string minus the maximum length of a valid substring
29 return len(s) - max_length
30
1class Solution {
2
3 /**
4 * This method calculates the minimum number of characters to remove from the string so that each character
5 * appears at least 'k' times in the remaining string.
6 *
7 * @param s The input string.
8 * @param k The minimum number of times each character should appear.
9 * @return The minimum number of characters to remove, or -1 if it's not possible.
10 */
11 public int takeCharacters(String s, int k) {
12 int[] charCounts = new int[3]; // Array to store the count of each character 'a', 'b', and 'c'.
13 int length = s.length(); // The length of the input string.
14
15 // Count occurrences of each character ('a', 'b', 'c').
16 for (int i = 0; i < length; ++i) {
17 // Increment the count for the current character.
18 charCounts[s.charAt(i) - 'a']++;
19 }
20
21 // Check if any character appears less than 'k' times.
22 for (int count : charCounts) {
23 if (count < k) {
24 return -1; // It's not possible to fulfill the condition.
25 }
26 }
27
28 int maxSubstringLength = 0; // Will hold the length of the longest valid substring.
29 int leftPointer = 0; // Points to the start of the current substring.
30
31 // Iterate over the characters of the string.
32 for (int rightPointer = 0; rightPointer < length; ++rightPointer) {
33 int currentCharIndex = s.charAt(rightPointer) - 'a'; // Index of the current character.
34 // Decrement the count of the current character since we're moving rightPointer.
35 charCounts[currentCharIndex]--;
36
37 // If count of the current character falls below 'k', readjust the leftPointer.
38 while (charCounts[currentCharIndex] < k) {
39 // Increment count of the character at leftPointer as it's no longer in current substring.
40 charCounts[s.charAt(leftPointer) - 'a']++;
41 // Move leftPointer to the right.
42 leftPointer++;
43 }
44
45 // Update the length of the longest valid substring found so far.
46 maxSubstringLength = Math.max(maxSubstringLength, rightPointer - leftPointer + 1);
47 }
48
49 // Return the minimum number of characters to remove, i.e., total length minus length of longest valid substring.
50 return length - maxSubstringLength;
51 }
52}
53
1class Solution {
2public:
3 int takeCharacters(string s, int k) {
4 int charCounts[3] = {0}; // Array to store counts of 'a', 'b', and 'c'
5
6 // Count the number of occurrences of each character
7 for (char& c : s) {
8 ++charCounts[c - 'a'];
9 }
10
11 // If any character appears less than k times, we cannot proceed
12 if (charCounts[0] < k || charCounts[1] < k || charCounts[2] < k) {
13 return -1;
14 }
15
16 int maxSubstringLength = 0; // To keep track of the maximum valid substring length
17 int windowStart = 0; // Start index of the current sliding window
18 int stringSize = s.size(); // Size of input string
19
20 // Iterate over each character in the string
21 for (int windowEnd = 0; windowEnd < stringSize; ++windowEnd) {
22 int currentCharIndex = s[windowEnd] - 'a'; // Get the index of current character (0, 1, or 2)
23 --charCounts[currentCharIndex]; // Reduce the count of the current character
24
25 // If the current character's count is below k, slide the window
26 while (charCounts[currentCharIndex] < k) {
27 ++charCounts[s[windowStart++] - 'a']; // Increment the count of the char getting out of the window
28 }
29
30 // Calculate the maximum valid substring length seen so far
31 maxSubstringLength = max(maxSubstringLength, windowEnd - windowStart + 1);
32 }
33
34 // The result is the size of the string minus the maximum valid substring length
35 return stringSize - maxSubstringLength;
36 }
37};
38
1/**
2 * Calculates the minimum number of characters that must be removed from a string
3 * so that every character that appears in the string does so both k times.
4 *
5 * @param {string} str - The input string.
6 * @param {number} k - The target frequency for each character.
7 * @return {number} The minimum number of characters to remove or -1 if not possible.
8 */
9function takeCharacters(str: string, k: number): number {
10 // Helper function to convert a character to an index (0 for 'a', 1 for 'b', etc.).
11 const getIndex = (char: string) => char.charCodeAt(0) - 'a'.charCodeAt(0);
12 // Array to count the frequency of each character, assuming only lowercase letters.
13 const frequencyCount = [0, 0, 0];
14 // Populate the frequency count array with the occurrences of each character in the input string.
15 for (const char of str) {
16 frequencyCount[getIndex(char)]++;
17 }
18 // If any character frequency is less than k, it's impossible to satisfy the condition, return -1.
19 if (frequencyCount.some(value => value < k)) {
20 return -1;
21 }
22 // Length of the input string.
23 const stringLength = str.length;
24 // Initialize the answer (maximum substring length satisfying the condition).
25 let maxSubstringLength = 0;
26 // Two pointers i and j to apply the sliding window technique.
27 for (let i = 0, j = 0; j < stringLength; j++) {
28 // Decrease the frequency count of the j-th character as it's now outside the window.
29 frequencyCount[getIndex(str[j])]--;
30 // Slide the start of the window forward while the current character's frequency is below k.
31 while (frequencyCount[getIndex(str[j])] < k) {
32 // Increase the frequency count of the i-th character as it's now included in the window.
33 frequencyCount[getIndex(str[i])]++;
34 i++;
35 }
36 // Calculate the maximum substring length by comparing with the current window size.
37 maxSubstringLength = Math.max(maxSubstringLength, j - i + 1);
38 }
39 // The answer is the difference between the string's length and the maximum substring length.
40 return stringLength - maxSubstringLength;
41}
42
Time and Space Complexity
Time Complexity
The time complexity of the given code is dictated by the for
loop, which iterates through the string s
; this operation is O(n)
, where n
is the length of the string. Inside the loop, the code performs constant-time operations, such as dictionary access, update, and comparison. However, the inner while
loop might seem to increase time complexity because it moves the index j
forward until a certain condition is met. But notice that j
can never be moved more than n
times over the entire execution of the outer loop, since each character is considered exactly once by both the outer loop and the inner while
loop across the entire runtime. Therefore, the time complexity remains O(n)
overall.
Space Complexity
The space complexity is governed by the Counter
object cnt
that stores the frequency of each character in the string. Since the number of distinct characters is constrained by the size of the alphabet in the conditional check "if any(cnt[c] < k for c in "abc"):
", the size of the counter will be O(1)
, as the alphabet size does not grow with the size of the input string. Hence, the overall space complexity remains constant, O(1)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used to implement priority queue?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first