We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Take K of Each Character From Left and Right

Number: 2599

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Meta

Problem Description

Given a string s that consists of the characters 'a', 'b', and 'c' and an integer k, you must determine the minimum number of minutes required to pick characters from either the leftmost or rightmost side so that you accumulate at least k of each character. If it is not possible to collect k of each character, return -1.

Key Insights

  • Instead of simulating left/right picks directly, consider the complementary contiguous subarray (the part that is not picked).
  • The problem is equivalent to finding the longest subarray that can be left untouched such that the remaining characters (those taken from the sides) still contain at least k of each character.
  • For each character ch in {'a', 'b', 'c'}, the window can contain at most (total_count[ch] - k) occurrences.
  • Use a sliding window approach to find the maximum length of such a valid subarray.

Space and Time Complexity

Time Complexity: O(n) – A single pass (or two, in the worst case) through the string using the sliding window. Space Complexity: O(1) – Only constant space is required to track counts for three characters.

Solution

The solution begins by counting the total occurrences of 'a', 'b', and 'c' in the string. If any character occurs less than k times, the answer is immediately -1. Next, we use the sliding window strategy to identify the longest contiguous subarray that can remain while ensuring that for each character ch, the subarray contains at most (total_counts[ch] - k) occurrences. This guarantee makes sure that the characters removed from the boundaries (the complement of this window) sum to at least k for each character. The answer is then the length of the string minus the length of this maximum valid window.

Code Solutions

# Python solution for "Take K of Each Character From Left and Right"
def takeCharacters(s: str, k: int) -> int:
    # Count total occurrences of each character in s
    total_counts = {'a': 0, 'b': 0, 'c': 0}
    for ch in s:
        total_counts[ch] += 1

    # If any character does not appear k times, return -1 immediately
    for ch in 'abc':
        if total_counts[ch] < k:
            return -1

    left = 0
    window_counts = {'a': 0, 'b': 0, 'c': 0}
    max_window_length = 0

    # Expand the window by iterating with the right pointer
    for right in range(len(s)):
        window_counts[s[right]] += 1

        # Shrink the window if any count exceeds total_counts[ch] - k
        while (window_counts['a'] > total_counts['a'] - k or
               window_counts['b'] > total_counts['b'] - k or
               window_counts['c'] > total_counts['c'] - k):
            window_counts[s[left]] -= 1
            left += 1

        # Update the maximum valid window length
        max_window_length = max(max_window_length, right - left + 1)

    # Minimum minutes is total length minus maximum valid subarray length
    return len(s) - max_window_length

# Example usage:
print(takeCharacters("aabaaaacaabc", 2))  # Expected Output: 8
← Back to All Questions