# Take K of Each Character From Left and Right
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/take-k-of-each-character-from-left-and-right)
Canonical: https://scaleengineer.com/dsa/problems/take-k-of-each-character-from-left-and-right
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Hash Table, String
---
## 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._

**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`

# Approaches
## Brute Force by Iterating All Prefix/Suffix Combinations
This approach directly translates the problem statement into a solution by checking every possible combination of characters taken from the left and right. We iterate through every possible prefix length and, for each, find the shortest suffix that, when combined with the prefix, satisfies the condition of having at least `k` of each character.
**Time:** O(N^2), where N is the length of the string. The nested loops iterate up to N times each. · **Space:** O(1) extra space, as we only store counts for three characters.
**Pros:** The logic is straightforward and follows directly from the problem description.; It is relatively easy to implement.
**Cons:** The time complexity of O(N^2) is too slow for the given constraints (N up to 10^5) and will likely result in a 'Time Limit Exceeded' error.
### Explanation
The brute-force method involves a nested loop structure. The outer loop iterates through all possible numbers of characters to take from the left, let's say `i`. The inner loop iterates through all possible numbers of characters to take from the right, `j`. For each pair `(i, j)`, we must ensure we don't take more characters than available (`i + j <= n`). We then count the characters in the chosen prefix and suffix and check if they meet the `k` requirement. To avoid re-calculating counts repeatedly, which would lead to an O(N^3) solution, we can calculate the prefix counts once per outer loop iteration and incrementally update the suffix counts in the inner loop. This optimization brings the complexity down to O(N^2).

```java
class Solution {
    public int takeCharacters(String s, int k) {
        int n = s.length();
        int[] totalCounts = new int[3];
        for (char c : s.toCharArray()) {
            totalCounts[c - 'a']++;
        }
        if (totalCounts[0] < k || totalCounts[1] < k || totalCounts[2] < k) {
            return -1;
        }
        if (k == 0) return 0;

        int minMinutes = n;
        // i = number of chars from left
        for (int i = 0; i <= n; i++) {
            int[] prefixCounts = new int[3];
            for (int p = 0; p < i; p++) {
                prefixCounts[s.charAt(p) - 'a']++;
            }
            
            int[] suffixCounts = new int[3];
            // j = number of chars from right
            for (int j = 0; j <= n - i; j++) {
                if (j > 0) {
                    suffixCounts[s.charAt(n - j) - 'a']++;
                }
                
                if (prefixCounts[0] + suffixCounts[0] >= k &&
                    prefixCounts[1] + suffixCounts[1] >= k &&
                    prefixCounts[2] + suffixCounts[2] >= k) {
                    minMinutes = Math.min(minMinutes, i + j);
                    break; // Smallest j for this i is found
                }
            }
        }
        return minMinutes;
    }
}
```
### Algorithm
1. First, handle the edge cases. If the total count of any character in `s` is less than `k`, it's impossible, so return -1. If `k` is 0, no characters need to be taken, so return 0.
2. Initialize `minMinutes` to the length of the string `n`, which is the maximum possible answer.
3. Iterate through all possible prefix lengths `i` from 0 to `n`.
4. For each `i`, calculate the counts of 'a', 'b', and 'c' in the prefix `s[0...i-1]`.
5. Then, for the current prefix, iterate through all possible suffix lengths `j` from 0 to `n-i`.
6. In this inner loop, incrementally build the suffix counts. For each `j`, add the character `s[n-j]` to the suffix counts.
7. Combine the prefix and suffix counts. Check if the counts of 'a', 'b', and 'c' are all at least `k`.
8. If the condition is met, we have found a valid combination of `i` characters from the left and `j` from the right. The total minutes are `i + j`. We update `minMinutes = min(minMinutes, i + j)`.
9. Since we are iterating `j` from smallest to largest, the first `j` that satisfies the condition for a given `i` will be the smallest. We can `break` the inner loop to optimize slightly.
10. After checking all `i`, `minMinutes` will hold the minimum total characters needed.

## Prefix/Suffix Counts and Binary Search
This approach improves upon the brute-force method by optimizing the search for the required suffix. For each possible prefix taken from the left, instead of linearly scanning for the shortest valid suffix from the right, we can use binary search. This is possible because the number of characters in a suffix is monotonically increasing with its length.
**Time:** O(N log N). Precomputation takes O(N). The main loop runs N times, with each iteration performing a binary search that takes O(log N) time. · **Space:** O(N) to store the prefix and suffix count arrays.
**Pros:** Significantly more efficient than the O(N^2) brute-force approach.; Guaranteed to pass within the time limits for the given constraints.
**Cons:** Requires O(N) extra space for the prefix and suffix count arrays.; More complex to implement than the brute-force approach.; While better than O(N^2), it is not the most optimal solution.
### Explanation
We begin by pre-calculating two arrays: `prefixCounts` and `suffixCounts`. `prefixCounts[i]` stores the character counts for the first `i` characters, and `suffixCounts[j]` stores the counts for the last `j` characters. This precomputation takes O(N) time.

Then, we iterate through each possible number of characters `i` to take from the left (from 0 to `n`). For each `i`, we determine the remaining number of 'a's, 'b's, and 'c's we still need to reach `k`. With these requirements, we can perform a binary search on the `suffixCounts` array to find the minimum number of characters `j` we need to take from the right. The total minutes for this prefix choice is `i + j`. We keep track of the minimum `i + j` found across all choices of `i`.

```java
class Solution {
    public int takeCharacters(String s, int k) {
        int n = s.length();
        if (k == 0) return 0;

        int[][] prefixCounts = new int[n + 1][3];
        for (int i = 0; i < n; i++) {
            prefixCounts[i + 1] = prefixCounts[i].clone();
            prefixCounts[i + 1][s.charAt(i) - 'a']++;
        }

        // Check if taking all characters is sufficient
        if (prefixCounts[n][0] < k || prefixCounts[n][1] < k || prefixCounts[n][2] < k) {
            return -1;
        }

        int[][] suffixCounts = new int[n + 1][3];
        for (int i = 0; i < n; i++) {
            suffixCounts[i + 1] = suffixCounts[i].clone();
            suffixCounts[i + 1][s.charAt(n - 1 - i) - 'a']++;
        }

        int minMinutes = n;
        for (int i = 0; i <= n; i++) {
            int[] needed = new int[3];
            for (int c = 0; c < 3; c++) {
                needed[c] = Math.max(0, k - prefixCounts[i][c]);
            }

            if (needed[0] == 0 && needed[1] == 0 && needed[2] == 0) {
                minMinutes = Math.min(minMinutes, i);
                continue;
            }

            int low = 0, high = n - i, bestJ = -1;
            while (low <= high) {
                int mid = low + (high - low) / 2;
                if (suffixCounts[mid][0] >= needed[0] && 
                    suffixCounts[mid][1] >= needed[1] && 
                    suffixCounts[mid][2] >= needed[2]) {
                    bestJ = mid;
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }

            if (bestJ != -1) {
                minMinutes = Math.min(minMinutes, i + bestJ);
            }
        }
        return minMinutes;
    }
}
```
### Algorithm
1. Handle edge cases: if total counts of any character are less than `k`, return -1. If `k=0`, return 0.
2. Precompute prefix counts: `prefixCounts[i]` will store the counts of 'a', 'b', 'c' in the prefix `s[0...i-1]`.
3. Precompute suffix counts: `suffixCounts[j]` will store the counts of 'a', 'b', 'c' in the suffix `s[n-j...n-1]`.
4. Initialize `minMinutes` to `n`.
5. Iterate `i` from 0 to `n`, representing taking a prefix of length `i`.
6. For each `i`, calculate the remaining characters needed: `needed_a = max(0, k - prefixCounts[i].a)`, and similarly for 'b' and 'c'.
7. If all `needed` counts are zero or less, it means the prefix of length `i` is sufficient. Update `minMinutes = min(minMinutes, i)`.
8. Otherwise, we need to find the smallest suffix length `j` that satisfies these `needed` counts. Since `suffixCounts[j]` is monotonic, we can use binary search on `j` in the range `[0, n-i]`.
9. The binary search will find the smallest `j` such that `suffixCounts[j]` provides the `needed` characters.
10. If a valid `j` is found, update `minMinutes = min(minMinutes, i + j)`.
11. After iterating through all `i`, return `minMinutes`.

## Optimal Sliding Window
The most efficient solution involves a clever change of perspective. Instead of minimizing the number of characters we take from the ends, we can think about maximizing the number of characters we *don't* take. The characters not taken must form a contiguous subarray in the middle of the original string. This transforms the problem into finding the longest subarray that meets certain criteria, which is a perfect scenario for the sliding window technique.
**Time:** O(N), where N is the length of the string. Both the `left` and `right` pointers traverse the string at most once. · **Space:** O(1), as we only use a fixed-size array (size 3) to store character counts.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1).; Provides an elegant and efficient solution to the problem.
**Cons:** The problem transformation from minimizing ends to maximizing the middle might not be immediately obvious.
### Explanation
Let the total counts of 'a', 'b', and 'c' in the string be `total_a`, `total_b`, and `total_c`. To satisfy the problem's condition, the characters we leave behind in the middle subarray must have counts no more than `total_a - k`, `total_b - k`, and `total_c - k`, respectively. If any of these target counts are negative, it's impossible to satisfy the condition, which we check at the beginning.

We can find the longest such subarray using a sliding window. We maintain a window `[left, right]` and the counts of characters within it. We expand the window by moving `right`. If at any point a character count in our window exceeds its allowed maximum, we shrink the window from the left by moving `left` forward until the window is valid again. In each step, we record the length of the current valid window and keep track of the maximum length found. The final answer is the total length of the string minus this maximum valid window length.

```java
class Solution {
    public int takeCharacters(String s, int k) {
        if (k == 0) {
            return 0;
        }
        int n = s.length();
        int[] totalCounts = new int[3];
        for (char c : s.toCharArray()) {
            totalCounts[c - 'a']++;
        }

        if (totalCounts[0] < k || totalCounts[1] < k || totalCounts[2] < k) {
            return -1;
        }

        int[] maxWindowCounts = new int[3];
        for (int i = 0; i < 3; i++) {
            maxWindowCounts[i] = totalCounts[i] - k;
        }

        int left = 0;
        int maxWindowLen = 0;
        int[] windowCounts = new int[3];

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

            while (windowCounts[0] > maxWindowCounts[0] ||
                   windowCounts[1] > maxWindowCounts[1] ||
                   windowCounts[2] > maxWindowCounts[2]) {
                windowCounts[s.charAt(left) - 'a']--;
                left++;
            }
            
            maxWindowLen = Math.max(maxWindowLen, right - left + 1);
        }

        return n - maxWindowLen;
    }
}
```
### Algorithm
1. First, handle edge cases. Calculate the total counts of 'a', 'b', 'c' in `s`. If any total is less than `k`, return -1. If `k=0`, return 0.
2. Reframe the problem: minimizing the characters taken from the ends is equivalent to maximizing the length of the contiguous subarray in the middle that is *left behind*.
3. Determine the constraints for this middle subarray. If we take `k` of each character, the remaining middle part must contain at most `total_a - k` 'a's, `total_b - k` 'b's, and `total_c - k` 'c's. Let's call these `max_a`, `max_b`, `max_c`.
4. The problem is now to find the longest subarray of `s` that satisfies these count constraints.
5. Use a sliding window approach with two pointers, `left` and `right`.
6. Initialize `left = 0`, `maxWindowLen = 0`, and `windowCounts` to zero.
7. Iterate `right` from 0 to `n-1`, expanding the window to the right. For each character `s[right]`, increment its count in `windowCounts`.
8. After expanding, check if the window is valid (i.e., if all character counts are within their `max` limits).
9. If the window is invalid (`windowCounts[c] > max_c` for any character `c`), shrink the window from the left by incrementing `left` and decrementing the count of `s[left]` until the window becomes valid again.
10. After each valid expansion (or post-shrinking), the window `s[left...right]` is valid. Update `maxWindowLen = max(maxWindowLen, right - left + 1)`.
11. After the loop, `maxWindowLen` holds the length of the longest possible middle part. The minimum minutes needed is `n - maxWindowLen`.

# Solutions
### Java

```java
class Solution { public int takeCharacters ( String s , int k ) { int [] cnt = new int [ 3 ]; int n = s . length (); for ( int i = 0 ; i < n ; ++ i ) { ++ cnt [ s . charAt ( i ) - 'a' ]; } if ( cnt [ 0 ] < k || cnt [ 1 ] < k || cnt [ 2 ] < k ) { return - 1 ; } int ans = 0 , j = 0 ; for ( int i = 0 ; i < n ; ++ i ) { int c = s . charAt ( i ) - 'a' ; -- cnt [ c ]; while ( cnt [ c ] < k ) { ++ cnt [ s . charAt ( j ++) - 'a' ]; } ans = Math . max ( ans , i - j + 1 ); } return n - ans ; } }
```

### Python

```python
class Solution : def takeCharacters ( self , s : str , k : int ) -> int : cnt = Counter ( s ) if any ( cnt [ c ] < k for c in "abc" ): return - 1 ans = j = 0 for i , c in enumerate ( s ): cnt [ c ] -= 1 while cnt [ c ] < k : cnt [ s [ j ]] += 1 j += 1 ans = max ( ans , i - j + 1 ) return len ( s ) - ans
```

### CPP

```cpp
class Solution {
public:
  int takeCharacters(string s, int k) {
    int cnt[3] = {0};
    for (char &c : s)
      ++cnt[c - 'a'];
    if (cnt[0] < k || cnt[1] < k || cnt[2] < k)
      return -1;
    int ans = 0, j = 0;
    int n = s.size();
    for (int i = 0; i < n; ++i) {
      int c = s[i] - 'a';
      --cnt[c];
      while (cnt[c] < k) {
        ++cnt[s[j++] - 'a'];
      }
      ans = max(ans, i - j + 1);
    }
    return n - ans;
  }
};

```