Take K of Each Character From Left and Right

Hard
807.

Take K of Each Character From Left and Right

Take K of Each Character From Left and Right is a hard coding problem on strings, hash table and prefix sum, asked in Amazon, Google and Rubrik interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var takeCharacters = function(s, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Take K of Each Character From Left and Right — Solution

Take K of Each Character From Left and Right solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Take K of Each Character From Left and Right is a hard coding problem on strings, hash table and prefix sum, asked in Amazon, Google and Rubrik interviews.

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

Hints for Take K of Each Character From Left and Right

  1. Hint 1

    What you take is a prefix and a suffix; what you leave behind is one contiguous middle block.

  2. Hint 2

    So minimise the taking by maximising the middle block you can leave.

  3. Hint 3

    A middle block is leavable when, for each character, the total outside it is at least k.

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

  1. Tally the whole string; if any character appears fewer than k times, return -1.
  2. Slide a window, tallying what is inside it.
  3. While some character has fewer than k copies outside the window, shrink from the left.
  4. 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

Java

public static int takeCharacters(String s, int k) {
    int n = s.length();
    int[] total = new int[3];
    for (int i = 0; i < n; i++) total[s.charAt(i) - 'a']++;
    for (int c = 0; c < 3; c++) if (total[c] < k) return -1;
    int[] cnt = new int[3];
    int l = 0, longest = 0;
    for (int r = 0; r < n; r++) {
        cnt[s.charAt(r) - 'a']++;
        while (total[0] - cnt[0] < k || total[1] - cnt[1] < k || total[2] - cnt[2] < k) {
            cnt[s.charAt(l) - 'a']--;
            l++;
        }
        longest = Math.max(longest, r - l + 1);
    }
    return n - longest;
}

C++

int takeCharacters(string s, int k) {
    int n = (int) s.size();
    int total[3] = { 0, 0, 0 };
    for (int i = 0; i < n; i++) total[s[i] - 'a']++;
    for (int c = 0; c < 3; c++) if (total[c] < k) return -1;
    int cnt[3] = { 0, 0, 0 };
    int l = 0, longest = 0;
    for (int r = 0; r < n; r++) {
        cnt[s[r] - 'a']++;
        while (total[0] - cnt[0] < k || total[1] - cnt[1] < k || total[2] - cnt[2] < k) {
            cnt[s[l] - 'a']--;
            l++;
        }
        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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets