2516. Take K of Each Character From Left and Right

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

Approach 01:

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
 public:
  int takeCharacters(string inputString, int minFrequency) {
    const int stringLength = inputString.length();
    int minDeletions = stringLength;
    vector<int> characterCount(3, 0);

    // Count the frequency of each character
    for (const char character : inputString)
      ++characterCount[character - 'a'];

    // If any character's frequency is less than minFrequency, return -1
    if (characterCount[0] < minFrequency || characterCount[1] < minFrequency || characterCount[2] < minFrequency)
      return -1;

    // Sliding window to find the minimum substring length
    for (int leftIndex = 0, rightIndex = 0; rightIndex < stringLength; ++rightIndex) {
      --characterCount[inputString[rightIndex] - 'a'];
      while (characterCount[inputString[rightIndex] - 'a'] < minFrequency)
        ++characterCount[inputString[leftIndex++] - 'a'];
      minDeletions = min(minDeletions, stringLength - (rightIndex - leftIndex + 1));
    }

    return minDeletions;
  }
};

class Solution:
    def takeCharacters(self, inputString: str, minFrequency: int) -> int:
        stringLength = len(inputString)
        minDeletions = stringLength
        characterCount = [0] * 3

        # Count the frequency of each character
        for character in inputString:
            characterCount[ord(character) - ord('a')] += 1

        # If any character's frequency is less than minFrequency, return -1
        if any(count < minFrequency for count in characterCount):
            return -1

        # Sliding window to find the minimum substring length
        leftIndex = 0
        for rightIndex in range(stringLength):
            characterCount[ord(inputString[rightIndex]) - ord('a')] -= 1
            while characterCount[ord(inputString[rightIndex]) - ord('a')] < minFrequency:
                characterCount[ord(inputString[leftIndex]) - ord('a')] += 1
                leftIndex += 1
            minDeletions = min(minDeletions, stringLength - (rightIndex - leftIndex + 1))

        return minDeletions

Time Complexity

• Frequency Count:

  Counting the frequency of characters in the string takes \( O(n) \), where \( n \) is the length of the input string.

• Sliding Window:

  The sliding window iterates through the string with two pointers (left and right). Each pointer moves from the start to the end of the string. Hence, this step also takes \( O(n) \).

• Overall Time Complexity:

  The overall time complexity is \( O(n) + O(n) = O(n) \).

Space Complexity

• Character Count:

  The characterCount vector stores counts for three characters (‘a’, ‘b’, ‘c’), which takes \( O(1) \) space.

• Auxiliary Variables:

  Other variables like leftIndex, rightIndex, and minDeletions take \( O(1) \) space.

• Overall Space Complexity:

  The overall space complexity is \( O(1) \).