Take K of Each Character From Left and Right - Problem

You are given a string s consisting of the characters 'a', 'b', and 'c' and a non-negative integer k. Each minute, you may take either the leftmost character of s, or the rightmost character of s.

Return the minimum number of minutes needed for you to take at least k of each character, or return -1 if it is not possible to take k of each character.

Input & Output

Example 1 — Basic Case

$ Input: s = "aabaaaacaabc", k = 2

› Output: 8

💡 Note: We need at least 2 of each character. Take "aaba" from left (4 chars) and "aabc" from right (4 chars). Total = 8 minutes.

Example 2 — Impossible Case

$ Input: s = "a", k = 1

› Output: -1

💡 Note: The string only contains 'a' but we need at least 1 'b' and 1 'c', which is impossible.

Example 3 — Zero Requirement

$ Input: s = "abc", k = 0

› Output: 0

💡 Note: We need 0 of each character, so no characters need to be taken. Answer is 0.

Constraints

1 ≤ s.length ≤ 10⁵
s consists of only characters 'a', 'b', and 'c'
0 ≤ k ≤ s.length

Visualization

Tap to expand

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to think in reverse: instead of finding the minimum characters to take from ends, find the maximum characters we can leave in the middle. Use sliding window to find the largest valid middle section. Best approach uses sliding window with Time: O(n), Space: O(1).

Common Approaches

✓ Brute Force - Try All Combinations

⏱️ Time: O(n²) Space: O(1)

For each possible number of characters taken from the left (0 to n), calculate how many we need from the right to satisfy the requirement. Check all combinations and find the minimum total.

Sliding Window - Maximum Middle Window

⏱️ Time: O(n) Space: O(1)

Instead of finding the minimum characters to take, we find the maximum characters we can leave in the middle. We need at least k of each character outside the middle window.

Brute Force - Try All Combinations — Algorithm Steps

Count total occurrences of each character
For each possible left count (0 to n), take those characters
Count remaining needed characters and try to fulfill from right side
Track minimum total characters needed

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Total

Count occurrences of each character in string

Try Splits

For each left position, count what we can get

Fill from Right

Take remaining needed characters from right side

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int min(int a, int b) {
    return a < b ? a : b;
}

int max(int a, int b) {
    return a > b ? a : b;
}

int solution(char* s, int k) {
    int n = strlen(s);
    
    // Count total characters
    int total_a = 0, total_b = 0, total_c = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'a') total_a++;
        else if (s[i] == 'b') total_b++;
        else total_c++;
    }
    
    // Check if solution is possible
    if (total_a < k || total_b < k || total_c < k) {
        return -1;
    }
    
    if (k == 0) {
        return 0;
    }
    
    int min_minutes = n;
    
    // Try all possible left counts
    for (int left = 0; left <= n; left++) {
        // Count characters taken from left
        int left_a = 0, left_b = 0, left_c = 0;
        for (int i = 0; i < left; i++) {
            if (s[i] == 'a') left_a++;
            else if (s[i] == 'b') left_b++;
            else left_c++;
        }
        
        // Calculate needed from right
        int need_a = max(0, k - left_a);
        int need_b = max(0, k - left_b);
        int need_c = max(0, k - left_c);
        
        // Try to get needed characters from right
        int right_a = 0, right_b = 0, right_c = 0;
        int right = 0;
        
        while (right < n - left && (right_a < need_a || right_b < need_b || right_c < need_c)) {
            char ch = s[n - 1 - right];
            if (ch == 'a') right_a++;
            else if (ch == 'b') right_b++;
            else right_c++;
            right++;
        }
        
        // Check if we got enough
        if (right_a >= need_a && right_b >= need_b && right_c >= need_c) {
            min_minutes = min(min_minutes, left + right);
        }
    }
    
    return min_minutes;
}

int main() {
    char s[100001];
    int k;
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    scanf("%d", &k);
    
    int result = solution(s, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Outer loop tries n positions, inner loop counts characters up to n positions

✓ Linear Growth

Space Complexity

O(1)

Only using variables to count characters, no extra data structures

✓ Linear Space

28.4K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Take K of Each Character From Left and Right - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler