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.
- Difficulty: Hard
- Topics: Strings, Hash Table, Prefix Sum, Sliding Window
- 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 <= 100000s consists only of 'a', 'b' and 'c'.0 <= k <= s.length
Hints for Take K of Each Character From Left and Right
Hint 1
What you take is a prefix and a suffix; what you leave behind is one contiguous middle block.
Hint 2
So minimise the taking by maximising the middle block you can leave.
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
- Tally the whole string; if any character appears fewer than
ktimes, return-1. - Slide a window, tallying what is inside it.
- While some character has fewer than
kcopies 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 = 0must 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 - longestJava
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