Take K of Each Character From Left and Right — Hard Problem & Solution

s contains only 'a', 'b' and 'c'. In one minute you may take one character from either the leftmost or the rightmost end of s and remove it.

Difficulty: Hard
Topics: Strings, Hash Table, Sliding Window, Prefix Sum
Asked at: Amazon, Google, Rubrik
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

s contains only 'a', 'b' and 'c'. In one minute you may take one character from either the leftmost or the rightmost end of s and remove it.

Return the minimum number of minutes needed to have taken at least k of each of the three characters, or -1 if it is impossible.

Example 1

Input: s = "aabaaaacaabc", k = 2
Output: 8
Explanation: Take four from the left and four from the right.

Example 2

Input: s = "a", k = 1
Output: -1
Explanation: There are no b or c to take.

Example 3

Input: s = "abc", k = 0
Output: 0
Explanation: Nothing needs taking.

Constraints

1 <= s.length <= 100000
s consists only of 'a', 'b' and 'c'.
0 <= k <= s.length

How to solve Take K of Each Character From Left and Right

Flip the problem around. The characters taken always form a prefix plus a suffix, so the untouched part is a single window. Maximise that window subject to every character having at least k copies outside it; the answer is n minus its length.

Approach

Tally the whole string; if any character appears fewer than k times, return -1.
Slide a window, tallying what is inside it.
While some character has fewer than k copies outside the window, shrink from the left.
Return n - longestValidWindow.

Why it works

Taking from the ends means the remaining string is contiguous, so the choice is exactly which window to leave. Growing the window removes characters from the outside, which can only violate the constraint, never repair it — the predicate is monotone in the left edge and a single forward-moving pointer suffices.

Complexity

Time — O(n)
Space — O(1)

Pitfalls

Trying to greedily take from whichever end is cheapest does not work — the choice interacts across the three characters.
k = 0 must return 0, which it does since the whole string is a valid window.
The impossibility check has to come first, or the shrink loop empties the window and still fails.

Reference solution

Python

def takeCharacters(s: str, k: int) -> int:
    n = len(s)
    total = {"a": 0, "b": 0, "c": 0}
    for ch in s:
        total[ch] += 1
    if any(total[c] < k for c in "abc"):
        return -1
    cnt = {"a": 0, "b": 0, "c": 0}
    l = 0
    longest = 0
    for r in range(n):
        cnt[s[r]] += 1
        while any(total[c] - cnt[c] < k for c in "abc"):
            cnt[s[l]] -= 1
            l += 1
        longest = max(longest, r - l + 1)
    return n - longest

JavaScript

var takeCharacters = function(s, k) {
    var n = s.length;
    var total = { a: 0, b: 0, c: 0 };
    for (var i = 0; i < n; i++) total[s.charAt(i)]++;
    if (total.a < k || total.b < k || total.c < k) return -1;
    var cnt = { a: 0, b: 0, c: 0 };
    var l = 0, longest = 0;
    for (var r = 0; r < n; r++) {
        cnt[s.charAt(r)]++;
        while (total.a - cnt.a < k || total.b - cnt.b < k || total.c - cnt.c < k) {
            cnt[s.charAt(l)]--;
            l++;
        }
        if (r - l + 1 > longest) longest = r - l + 1;
    }
    return n - longest;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue