LeetCode 2516 - Take K of Each Character From Left and Right

Difficulty: 🟡 Medium
Topics: Hash Table, String, Sliding Window

Solution

Problem Understanding

The problem asks us to determine the minimum number of characters to take from either end of a string s consisting only of the letters 'a', 'b', and 'c' so that we collect at least k of each character. You are allowed to take characters from the leftmost or rightmost position of the string in each step. The output is the total number of characters taken, or -1 if it is impossible to achieve k of each character.

Inputs are:

s, a string of length up to 10^5 consisting only of 'a', 'b', 'c'.
k, a non-negative integer indicating the minimum count required for each character.

The output is a single integer representing the minimum number of steps, or -1 if the requirement cannot be satisfied.

The problem constraints tell us that the string length is large enough that brute-force enumeration of all left-right combinations is not feasible, so we need a more efficient approach. The edge cases that may trip up naive implementations include:

k is 0, which should trivially return 0 because no characters are needed.
The total count of any character in s is less than k, which makes it impossible to satisfy the requirement.
k is exactly equal to the number of some characters in the string, requiring us to take almost all characters.

Approaches

Brute Force Approach

A naive approach would be to try all combinations of taking i characters from the left and j characters from the right for all valid i and j such that i + j <= len(s). For each combination, count how many 'a', 'b', and 'c' are collected. If all counts reach k, update the minimum number of characters taken.

This approach is correct because it examines every possible way to take characters, but it is too slow. There are O(n^2) possible (i, j) pairs for a string of length n, which would be ~10^10 operations in the worst case. Clearly, this is not feasible.

Optimal Approach

Key observation: Since we can only take characters from either end, the problem can be reframed as a sliding window problem. Instead of counting what we take, we can count what we leave in the middle.

Let the total count of each character be total_counts.
We need at least k of each character, so we can afford to leave up to total_counts[c] - k of each character inside.
We then try to find the longest contiguous substring where no character exceeds total_counts[c] - k. This substring represents the characters we do not take.
The minimum number of characters we take is len(s) - length_of_this_substring.

This is efficient because we can use a sliding window to track character counts and find the longest valid window in O(n) time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(1)	Check all left-right combinations
Optimal (Sliding Window)	O(n)	O(1)	Find longest middle substring that can remain

Algorithm Walkthrough

Count total occurrences of 'a', 'b', 'c' in s.
Check feasibility: If any character count is less than k, return -1.
Initialize max_window_len = 0, and two pointers left = 0.
Iterate with right from 0 to len(s)-1:

Include s[right] in the current window count.
While the current window count exceeds total_counts[c] - k for any character, shrink the window from the left until it becomes valid.
Update max_window_len if the current window is valid and longer than previous.

The minimum number of characters to take is len(s) - max_window_len.
Return this value.

Why it works: The invariant is that at every step, the window represents a contiguous substring we could leave in s without violating the requirement of taking at least k of each character. By maximizing the length of this substring, we minimize the number of characters we need to take from the ends.

Python Solution

from collections import Counter

class Solution:
    def takeCharacters(self, s: str, k: int) -> int:
        total_counts = Counter(s)
        # Check if it is possible
        if total_counts['a'] < k or total_counts['b'] < k or total_counts['c'] < k:
            return -1
        
        n = len(s)
        max_window_len = 0
        window_counts = Counter()
        left = 0
        
        for right in range(n):
            window_counts[s[right]] += 1
            # Shrink window until valid
            while (window_counts['a'] > total_counts['a'] - k or
                   window_counts['b'] > total_counts['b'] - k or
                   window_counts['c'] > total_counts['c'] - k):
                window_counts[s[left]] -= 1
                left += 1
            max_window_len = max(max_window_len, right - left + 1)
        
        return n - max_window_len

Explanation: We first count the total number of each character. If any total is less than k, we immediately return -1. Then we use a sliding window to find the longest valid substring that can remain, adjusting the left pointer when a character exceeds its allowed remaining count. Finally, len(s) - max_window_len gives the minimum number of characters needed.

Go Solution

func takeCharacters(s string, k int) int {
    count := map[byte]int{'a':0, 'b':0, 'c':0}
    for i := 0; i < len(s); i++ {
        count[s[i]]++
    }
    if count['a'] < k || count['b'] < k || count['c'] < k {
        return -1
    }
    
    n := len(s)
    maxWindow := 0
    window := map[byte]int{'a':0, 'b':0, 'c':0}
    left := 0
    
    for right := 0; right < n; right++ {
        window[s[right]]++
        for window['a'] > count['a'] - k || window['b'] > count['b'] - k || window['c'] > count['c'] - k {
            window[s[left]]--
            left++
        }
        if right - left + 1 > maxWindow {
            maxWindow = right - left + 1
        }
    }
    
    return n - maxWindow
}

Explanation: Similar logic as Python. We use maps to track counts. Go maps are nil-safe, but we initialize all keys to ensure no runtime errors. The sliding window shrinks when a character exceeds the allowable remaining count.

Worked Examples

Example 1: s = "aabaaaacaabc", k = 2

Total counts: a:7, b:2, c:3
Allowed remaining: a:5, b:0, c:1
Sliding window process:

left	right	window_counts	valid?	max_window_len
0	0	a:1	yes	1
0	1	a:2	yes	2
0	2	a:2,b:1	no	2
...	...	...	...	...
final	7	window "aaaaca"	yes	5

Minimum characters to take: 12 - 4 = 8

Example 2: s = "a", k = 1

Total counts: a:1, b:0, c:0 → impossible, return -1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass sliding window over string of length n
Space	O(1)	Only three characters, so fixed-size counters

The solution is linear and space-efficient. The main insight is that the sliding window operates in constant space relative to input size.

Test Cases

# Provided examples
assert Solution().takeCharacters("aabaaaacaabc", 2) == 8  # Example 1
assert Solution().takeCharacters("a", 1) == -1            # Example 2

# Edge cases
assert Solution().takeCharacters("abcabcabc", 3) == 9     # Need all characters
assert Solution().takeCharacters("abcabcabc", 0) == 0     # k = 0, take 0
assert Solution().takeCharacters("aaaabbbbcccc", 2) == 6  # Take minimal from ends

# Single character long string