• Leetcode POTDs

Problem 2516 Take K of Each Character From Left and Right

Problem Statement

Link - Problem 2516

Question

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 <= 105
• s consists of only the letters 'a', 'b', and 'c'.
• 0 <= k <= s.length

Solution

class Solution {
public:
    int takeCharacters(string s, int k) {
        vector<int> count(3, 0);
        int n = s.length();

        for (char c : s) {
            count[c - 'a']++;
        }

        for (int i = 0; i < 3; i++) {
            if (count[i] < k)
                return -1;
        }

        vector<int> window(3, 0);
        int left = 0, max_window = 0;

        for (int right = 0; right < n; right++) {
            window[s[right] - 'a']++;

            while (left <= right && (count[0] - window[0] < k || count[1] - window[1] < k || count[2] - window[2] < k)) {
                window[s[left] - 'a']--;
                left++;
            }

            max_window = max(max_window, right - left + 1);
        }

        return n - max_window;
    }
};

Complexity Analysis

| Algorithm                        | Time Complexity | Space Complexity |
| -------------------------------- | --------------- | ---------------- |
| Sliding Window with Two Pointers | O(n)            | O(1)             |

Explanation

Intial Thoughts

My initial thoughts on this problem revolve around identifying the characters at both ends of the string. This problem asks us to find the minimum number of minutes to get at least k of each character, so we need to think about the optimal strategy to take characters from both the left and right sides. I think about this like trying to solve a puzzle where we have to balance taking characters from both sides to minimize the total time. I also consider how choosing characters from one side affects our ability to get enough characters from the other side.

Intuitive Analysis

Upon deeper analysis, I realize that my initial intuition about balancing the characters from both sides is key. By maintaining a sliding window that captures our total count of each character, we ensure we know exactly how many we have of each character. The key insight here is to understand that taking characters from the left and right sides affects the total number of characters we have. We should keep removing characters from the left until we have enough characters of each type. We need to consider the characters we cannot move to the left side without affecting our total count of characters, indicating that we cannot take less than a certain number of characters. We continuously update our maximum window count to find the minimum number of minutes needed.

1. Intuition

• The problem can be solved by finding the minimum window that contains at least k characters of each type.
• We can use a sliding window approach to find this minimum window.
• The key insight is to maintain a count of characters outside the window and ensure it’s greater than or equal to k.
• If the count of any character outside the window is less than k, we need to expand the window.
• We can use two pointers, left and right, to represent the window and expand it accordingly.
• The minimum number of minutes needed is the total length of the string minus the maximum window size.
• This approach ensures we consider all possible windows and find the minimum one that satisfies the condition.

2. Implementation

• Initialize a count array count to store the total count of each character in the string s.
• Use a for loop to iterate over the string s and update the count array count.
• Check if the count of any character is less than k and return -1 if true.
• Initialize a window array window to store the count of each character in the current window.
• Use two pointers, left and right, to represent the window and expand it accordingly.
• Use a while loop to check if the count of any character outside the window is less than k and expand the window if true.
• Update the maximum window size max_window accordingly.
• Return the total length of the string minus the maximum window size max_window.

Complexity Analysis

Time Complexity:

• The time complexity of this solution is O(n) due to the two main loops that iterate through the string s. The first loop counts the frequency of each character, while the second loop is the sliding window with two pointers.
• The dominant operations are the incrementing of count and window arrays, as well as the comparisons in the while loop.
• The justification for O(n) is that the number of operations grows linearly with the size of the input string n, as we only make a constant amount of operations for each character in the string.

Space Complexity:

• The space complexity of this solution is O(1) as the space usage does not grow with the size of the input string.
• The only data structures used are the count and window arrays, both of size 3, which are constants.
• The justification for O(1) is that the memory usage remains constant regardless of the size of the input string n.

Footnote

This question is rated as Medium difficulty.

Hints

Start by counting the frequency of each character and checking if it is possible.

If you take x characters from the left side, what is the minimum number of characters you need to take from the right side? Find this for all values of x in the range 0 ≤ x ≤ s.length.

Use a two-pointers approach to avoid computing the same information multiple times.

Similar Questions: