문제 링크

내 코드

생각나는 아이디어가 없다.

Solution Approach 2.

• Left와 Right에서 뺀다. $\rightarrow$ 가운데 몸통(window) 하나로 생각해보기..!!!

• ms, MB

Solution

Approach 1: Recursion (Time Limit Exceeded)

• ms, MB
• Complexity
  • Let $n$ be the length of the string.
  • Time Complexity: $O(2^n)$
  • Space Complexity: $O(n)$

class Solution {
    int minMinutes = INT_MAX;

public:
    int takeCharacters(string s, int k) {
        if (k == 0) return 0;
        vector<int> count(3, 0);
        solve(s, k, 0, s.length() - 1, count, 0);
        return minMinutes == INT_MAX ? -1 : minMinutes;
    }

private:
    void solve(string& s, int k, int left, int right, vector<int> count,
               int minutes) {
        // Base case: check if we have k of each character
        if (count[0] >= k && count[1] >= k && count[2] >= k) {
            minMinutes = min(minMinutes, minutes);
            return;
        }
        // If we can't take more characters
        if (left > right) return;

        // Take from left
        vector<int> leftCount = count;
        leftCount[s[left] - 'a']++;
        solve(s, k, left + 1, right, leftCount, minutes + 1);

        // Take from right
        vector<int> rightCount = count;
        rightCount[s[right] - 'a']++;
        solve(s, k, left, right - 1, rightCount, minutes + 1);
    }
};

Approach 2: Sliding Window

The core idea of this solution is to identify the largest removable window in the string such that removing it still leaves at least k occurrences of each character 'a', 'b', and 'c'.

To achieve this, we iterate through the string to locate the window using two pointers, left and right.

• The pointer right progressively expands the window by including characters, one at a time, into the current window.
• Simultaneously, the pointer left is used to shrink the window whenever the current configuration violates the condition that at least k occurrences of each character must remain outside the window.

As we increment right, we add the character at that position to the window and update the counts. If adding this character results in too few occurrences of any character outside the window, we increment left to remove characters from the start of the window, restoring the required character counts outside the window.

Whenever a valid window is identified—where the counts of 'a', 'b', and 'c' outside the window are all at least k—we calculate the size of the current window. If this size is larger than previously identified windows, we update maxWindow. The final result is derived by subtracting the size of the largest valid window (maxWindow) from the total string length, effectively calculating the smallest portion of the string that must be removed.

After completing the iteration, the minimum number of minutes required is given by subtracting the size of the largest valid window from the total length of the string.

More mathematically, this can be expressed as:
$Minimum Minutes=Length of String−Size of the Largest Valid Window$

For example, suppose the string is "aabbccabc", and k = 2:

• 14ms, 12.02MB
• Complexity
  • Let $n$ be the length of the string.
  • Time Complexity: $O(n)$
  • Space Complexity: $O(3) = O(1)$

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

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

        // Check if we have enough characters
        for (int i = 0; i < 3; i++) {
            if (count[i] < k) return -1;
        }

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

        // Find the longest window that leaves k of each character outside
        for (int right = 0; right < n; right++) {
            window[s[right] - 'a']++;

            // Shrink window if we take too many characters
            while (left <= right &&
                   (count[0] - window[0] < k || count[1] - window[1] < k ||
                    count[2] - window[2] < k)) {
                window[s[left] - 'a']--;
                left++;
            }

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

        return n - maxWindow;
    }
};