2516. Take K of Each Character From Left and Right

MediumHash TableStringSliding Window

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 pointer j to represent the start of the window we want to remove. If after removing a character at i, we find that any character's count is below k, we move the pointer j forward to add characters back to the window, until each character's count is at least k 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 and j, to iterate through the string. i will go from the start to the end of the string, while j will mark the beginning of the sliding window. Initialize ans to 0, which will keep track of the maximum window size found that maintains at least k 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 the Counter, as removing the character s[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 than k, it means we need to move the other pointer j forwards to expand the sliding window and add characters back to the count, until all counts are again at least k.
- During this adjustment, if s[j] is added back to the window, increase its count in the Counter and move j forward by 1.
- Ensure that through these adjustments, the count of every character outside the window remains at least k.
Calculate Maximum Window: After each iteration, update ans with the size of the current window if it is larger than the previous ans. This window represents the maximum size that left at least k 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 Evaluator

Example 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:
```
{'a': 2, 'b': 3, 'c': 1}
```
Check Possibility:
- Since 'c' only has one instance and k is 2, it's not possible to have at least k instances of 'c' remaining after any removals. Therefore, we immediately return -1.

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:

{'a': 2, 'b': 3, 'c': 2}

Check Possibility:
- Every character 'a', 'b', and 'c' occurs at least k times, so it's possible to proceed.
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 removing s[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 adjust j, as all counts are still at least k.
  - i = 1: Remove 'b', Counter becomes {'a': 1, 'b': 2, 'c': 2}. No need to adjust j, only when a letter goes below k do we adjust j.
  - 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 below k, so we start moving j 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 move j forward as it would decrease the count of 'b' which is already at minimum allowed for k.
  By i = 3, the count of 'b' can't be allowed to decrease any further without also decreasing j.
Calculate Maximum Window:
- The window size with i = 3 and j = 1 is 3 - 1 = 2. Update ans to 2.
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 is 7 - 3 = 4. Thus, it takes a minimum of 4 minutes to remove characters such that at least k instances of each remain.

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of the following problems can be solved with backtracking (select multiple)

Generating subsets

Generating random numbers

Generating permutations

Sorting integers