Taro Logo

Take K of Each Character From Left and Right

Medium
Asked by:
Profile picture
Profile picture
Profile picture
97 views
Topics:
StringsTwo PointersSliding Windows

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.

Example 1:

Input: s = "aabaaaacaabc", k = 2
Output: 8
Explanation: 
Take three characters from the left of s. You now have two 'a' characters, and one 'b' character.
Take five characters from the right of s. You now have four 'a' characters, two 'b' characters, and two 'c' characters.
A total of 3 + 5 = 8 minutes is needed.
It can be proven that 8 is the minimum number of minutes needed.

Example 2:

Input: s = "a", k = 1
Output: -1
Explanation: It is not possible to take one 'b' or 'c' so return -1.

Constraints:

  • 1 <= s.length <= 105
  • s consists of only the letters 'a', 'b', and 'c'.
  • 0 <= k <= s.length

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What are the possible characters in the string, and is the input string guaranteed to contain at least k occurrences of each of these characters?
  2. If it's impossible to take k of each character from both ends, what should I return?
  3. Is k guaranteed to be a non-negative integer, and is it always less than or equal to half the length of the input string?
  4. If there are multiple solutions (multiple valid substrings), should I return any valid solution, or the shortest/longest one?
  5. Could you provide an example of what a valid input string would look like given a certain value of 'k'?

Brute Force Solution

Approach

The brute force method for this problem involves trying every possible combination of taking characters from the left and right sides of the string. We'll check each combination to see if it satisfies the requirement of having at least K occurrences of each character. The best solution is then selected from all the valid ones.

Here's how the algorithm would work step-by-step:

  1. Start by considering taking zero characters from the left side of the string.
  2. Then, for each possibility of characters taken from the left side, try all possible numbers of characters taken from the right side, starting from zero.
  3. For each combination of characters from the left and right, check if that selection contains at least 'K' of each distinct character.
  4. If the selection has enough of each character, record the length of that substring (the total number of characters taken from both sides).
  5. If the selection doesn't contain enough of each character, discard it and move on to the next possible number of characters from the right side.
  6. Repeat this process until you have checked all possible combinations of characters from the left and right.
  7. Finally, choose the shortest recorded length, since we want to take the minimum number of characters that meet the requirement. If no combination meets the requirement, indicate that it's impossible.

Code Implementation

def take_k_of_each_character_brute_force(input_string, k_value):
    minimum_characters_taken = float('inf')
    string_length = len(input_string)

    for left_characters_taken in range(string_length + 1):
        for right_characters_taken in range(string_length - left_characters_taken + 1):
            # Generate substring based on left and right chars taken
            substring = input_string[:left_characters_taken] + input_string[string_length - right_characters_taken:]

            character_counts = {}
            for character in substring:
                character_counts[character] = character_counts.get(character, 0) + 1

            is_valid = True

            # Check if all characters meet minimum k requirement
            for character in set(input_string):
                if character_counts.get(character, 0) < k_value:
                    is_valid = False

                    break

            if is_valid:
                # Update minimum characters if a smaller valid substring is found
                minimum_characters_taken = min(minimum_characters_taken, left_characters_taken + right_characters_taken)

    if minimum_characters_taken == float('inf'):
        return -1
    else:
        return minimum_characters_taken

Big(O) Analysis

Time Complexity
O(n^2) – The brute force approach iterates through all possible combinations of left and right substrings. The outer loop considers taking 0 to n characters from the left side of the string. The inner loop, nested within the outer loop, considers taking 0 to n - left characters from the right side. For each combination, a check is performed to verify if the selected substring contains at least K occurrences of each distinct character which takes O(1) time since the number of distinct characters is fixed. Therefore, the total operations are approximately n * n, simplifying to O(n^2).
Space Complexity
O(1) – The provided brute force solution primarily utilizes a constant amount of extra space. It needs to store a count of each distinct character to check if the requirement of having at least K occurrences is met. Since the number of distinct characters is limited (e.g., 26 for lowercase English letters), this character count storage remains constant regardless of the input string's length (N). Thus, the auxiliary space used does not scale with the input size, resulting in O(1) space complexity.

Optimal Solution

Approach

The goal is to find the shortest portion of the string to remove such that the remaining string has at least K occurrences of each character. We will efficiently find this shortest portion by focusing on what needs to remain rather than exhaustively searching for what to remove.

Here's how the algorithm would work step-by-step:

  1. First, count how many times each character appears in the whole string.
  2. If the whole string doesn't have enough of one of the characters, then it's impossible, so stop.
  3. Figure out how many of each character we need to keep (at least K).
  4. Now, imagine two 'pointers', one starting at the beginning and one at the end of the string. These pointers mark the beginning and end of the substring we will keep.
  5. Move the right pointer from left to right until the substring between the two pointers satisfies the requirement for each character.
  6. Once we found a valid substring, try to shrink the substring from the left. Move the left pointer from left to right until one of the character counts falls below the required amount.
  7. We found a potentially smaller substring, record its length.
  8. Continue moving the right pointer to expand the substring until all character requirements are met again.
  9. Repeat shrinking from the left and expanding from the right to try to find the smallest possible substring. Keep track of the smallest length found so far.
  10. Once the right pointer reaches the end of the string, we've checked all possible substrings and found the shortest substring that contains at least K occurrences of each character. The length of substring that needs to be removed is the original length of string minus the shortest substring length.

Code Implementation

def take_k_of_each_character(input_string, k_value):
    string_length = len(input_string)
    character_counts = {}
    for char in input_string:
        character_counts[char] = character_counts.get(char, 0) + 1

    for char_count in character_counts.values():
        if char_count < k_value:
            return -1

    required_character_counts = {}
    for char in character_counts:
        required_character_counts[char] = k_value

    left_pointer = 0
    right_pointer = 0
    min_removed_length = string_length
    current_character_counts = {}

    while right_pointer < string_length:
        current_character = input_string[right_pointer]
        current_character_counts[current_character] = current_character_counts.get(current_character, 0) + 1

        while all(current_character_counts.get(char, 0) >= required_character_counts[char] for char in required_character_counts): 
            # Found a valid substring, try to shrink from the left
            min_removed_length = min(min_removed_length, string_length - (right_pointer - left_pointer + 1))

            left_character = input_string[left_pointer]
            current_character_counts[left_character] -= 1
            left_pointer += 1

        right_pointer += 1

    return min_removed_length

Big(O) Analysis

Time Complexity
O(n) – The algorithm iterates through the string using two pointers, 'left' and 'right'. The 'right' pointer moves from left to right once through the entire string of length n. The 'left' pointer also moves from left to right, but each element is only visited by either the left or right pointer, not both, during the shrinking phase. Therefore, each pointer moves at most n times, resulting in a linear time complexity, O(n).
Space Complexity
O(1) – The algorithm uses a constant amount of extra space. It stores counts of each character in the string, which is bounded by the number of unique characters (a constant in this case, assuming a fixed character set like ASCII). It also stores a few integer variables for left and right pointers and shortest length found, but the space required for these variables does not depend on the input string length N. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Empty string input
How to Handle:
Return an empty string immediately as no characters can be taken.
k is zero
How to Handle:
Return an empty string since no characters need to be taken.
k is greater than the count of a character in the string
How to Handle:
Return an empty string immediately as the number of left and right characters to take exceeds the size of at least one character.
String contains characters other than those specified.
How to Handle:
The program should filter or throw error based on problem specification.
String length is very large, causing potential memory issues when creating prefix/suffix character counts
How to Handle:
Consider an optimized sliding window approach to minimize memory footprint.
No solution exists (it's impossible to take k of each character)
How to Handle:
Return an empty string when the solution cannot be found.
k is a negative number
How to Handle:
Throw an IllegalArgumentException since k cannot be negative.
All characters in the string are the same
How to Handle:
Return an empty string since it will never be possible to make pairs from each side, as there needs to be at least two different characters.