Take K of Each Character From Left and Right [Medium] — Middle Window

Problem Statement

String s contains 'a','b','c'. In each minute you can take the leftmost or rightmost character. Return minimum minutes to have at least k of each. Return -1 if impossible.

Input: s="aabaaaacaabc", k=2 → Output: 8

Intuition

Complement: find the longest middle window you can skip such that the characters outside (taken from ends) still have >= k of each.

Solutions

Python

from collections import Counter

def takeCharacters(s: str, k: int) -> int:
    total = Counter(s)
    if any(total[c] < k for c in 'abc'):
        return -1
    n = len(s)
    # Max window we can leave out
    have = {'a': total['a']-k, 'b': total['b']-k, 'c': total['c']-k}
    window = Counter()
    left = best = 0
    for right, c in enumerate(s):
        window[c] += 1
        while window[c] > have[c]:
            window[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return n - best

C++

int takeCharacters(string s, int k) {
    int cnt[3]={}, n=s.size();
    for(char c:s) cnt[c-'a']++;
    if(cnt[0]<k||cnt[1]<k||cnt[2]<k) return -1;
    int have[3]={cnt[0]-k,cnt[1]-k,cnt[2]-k};
    int win[3]={}, left=0, best=0;
    for(int r=0;r<n;r++){
        win[s[r]-'a']++;
        while(win[s[r]-'a']>have[s[r]-'a']) win[s[left++]-'a']--;
        best=max(best,r-left+1);
    }
    return n-best;
}

Complexity

Time: O(n), Space: O(1)