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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Take K of Each Character From Left and Right

Difficulty: Medium

Problem Description

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.

Key Insights

  • We need to count how many 'a', 'b', and 'c' characters can be taken from both ends of the string.
  • A sliding window approach can help us efficiently evaluate different segments of the string.
  • The total number of characters taken from both ends should be minimized while ensuring we have at least k of each character.
  • If the total occurrences of any character in the input string is less than k, then it is impossible to fulfill the requirement.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can use a two-pointer technique to evaluate how many characters we can take from both the left and right ends of the string. We will maintain a count of characters taken and check if we can reach the required k characters for each type. The goal is to minimize the total number of characters taken.

  1. Initialize two pointers at the start and end of the string.
  2. Use a hashmap to keep track of the counts of 'a', 'b', and 'c' as we take characters from both ends.
  3. Expand the window from both sides, and for each combination of taken characters, check if it meets the k requirement.
  4. Track the minimum number of characters taken.

Code Solutions

def takeCharacters(s: str, k: int) -> int:
    from collections import Counter

    n = len(s)
    count = Counter(s)
    
    # If any character count is less than k, return -1
    if count['a'] < k or count['b'] < k or count['c'] < k:
        return -1

    left = 0
    result = float('inf')
    
    # Sliding window approach
    for right in range(n):
        count[s[right]] -= 1
        
        # Move the left pointer to maintain at least k of each character
        while count['a'] >= k and count['b'] >= k and count['c'] >= k:
            result = min(result, right - left + 1)
            count[s[left]] += 1
            left += 1

    return n - result if result != float('inf') else -1
← Back to All Questions