Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7

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:

1
2
3

Input: s = "a", k = 1
Output: -1
Explanation: It is not possible to take one 'b' or 'c' so return -1.

Solution

Method 1 - Sliding Window

Here is the approach:

  1. Initial Counts: Count the occurrences of each character (‘a’, ‘b’, ‘c’) in the string s using a dictionary. If any character has less than k occurrences, it is impossible to meet the requirement, so return -1.
  2. Sliding Window: Use a sliding window approach to find the smallest window that does not meet the requirement. Maintain a window of characters and adjust it until you have at least k occurrences of each character. Keep track of the minimum window size needed to achieve the goal.
  3. Adjust Window:
    • Expand the window by including characters from the start of the string and decrement their counts.
    • If the count of any character goes below k, contract the window from the left until the count meets the requirement again.
    • Record the minimum window size that needs to be excluded.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
    public int takeCharacters(String s, int k) {
        int n = s.length();
        int left = 0, ans = n + 1, windowSz = 0;
        Map<Character, Integer> charCnt = new HashMap<>();

        // Count total occurrences of each character
        for (int i = 0; i < n; i++) {
            charCnt.put(s.charAt(i), charCnt.getOrDefault(s.charAt(i), 0) + 1);
        }

        // If any character count is less than k, return -1
        if (charCnt.getOrDefault('a', 0) < k || charCnt.getOrDefault('b', 0) < k || charCnt.getOrDefault('c', 0) < k) {
            return -1;
        }

        for (int right = 0; right < n; right++) {
            char curr = s.charAt(right);
            charCnt.put(curr, charCnt.get(curr) - 1);
            windowSz++;

            // Shrink the window until we fulfill the requirement
            while (charCnt.get(curr) < k) {
                charCnt.put(s.charAt(left), charCnt.get(s.charAt(left)) + 1);
                windowSz--;
                left++;
            }
            
            ans = Math.min(ans, n - windowSz);
        }

        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution:
    def takeCharacters(self, s: str, k: int) -> int:
        length = len(s)
        left, ans, windowSz = 0, length + 1, 0
        charCnt: Dict[str, int] = {'a': 0, 'b': 0, 'c': 0}

        # Count total occurrences of each character
        for char in s:
            charCnt[char] += 1

        # If any character count is less than k, return -1
        if charCnt['a'] < k or charCnt['b'] < k or charCnt['c'] < k:
            return -1

        for right in range(length):
            curr = s[right]
            charCnt[curr] -= 1
            windowSz += 1

            # Shrink the window until we fulfill the requirement
            while charCnt[curr] < k:
                charCnt[s[left]] += 1
                windowSz -= 1
                left += 1

            ans = min(ans, length - windowSz)

        return ans

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string s, since we process each character at most twice (once when expanding and once when contracting the window).
  • 🧺 Space complexity: O(1), since the additional space used is constant (only a few variables and a fixed-size dictionary are used).