leetcode - 2516. Take K of Each Character From Left and Right

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.

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 <= 10^5
s consists of only the letters 'a', 'b', and 'c'.
0 <= k <= s.length

Solution

Backtrace (TLE)

Use backtrace to iterate all the possibilities. Each time, take one from leftmost or rightmost, compare and pick the minimum one.

Time complexity: $o(n^2)$
Space complexity: $o(n)$

Sliding window

Solved after help.

Instead of trying to find the minimum number from the end, we could find the longest substring in the middle, where the substring contains no more than some characters. For example, in the first example, it has {a: 8, b: 2, c:2} characters. If we could find the substring in the middle that contains at most {a: 6, b: 0, c: 0}, then len(s) - len(substring) would be our answer.

So now the problem turns into finding the longest substring that contains at most these characters. To solve this problem, we could use a sliding window.

Time complexity: $o(n)$
Space complexity: $o(1)$

Code

Backtrace (TLE)

class Solution:
    def takeCharacters(self, s: str, k: int) -> int:
        def helper(char_cnt: dict, cur_left: int, cur_right: int) -> int:
            if sum(char_cnt.values()) == 0:
                return 0
            if cur_left > cur_right:
                return -1
            # take from leftmost
            left_char = s[cur_left]
            old_char_cnt = char_cnt[left_char]
            if char_cnt[left_char] != 0:
                char_cnt[left_char] -= 1
            left_val = 1 + helper(char_cnt, cur_left + 1, cur_right)
            # restore back
            char_cnt[left_char] = old_char_cnt 
            # take from rightmost
            right_char = s[cur_right]
            old_char_cnt = char_cnt[right_char]
            if char_cnt[right_char] != 0:
                char_cnt[right_char] -= 1
            right_val = 1 + helper(char_cnt, cur_left, cur_right - 1)
            # restore back
            char_cnt[right_char] = old_char_cnt
            if left_val == 0 and right_val == 0:
                return -1
            if left_val == 0:
                return right_val
            if right_val == 0:
                return left_val
            return min(left_val, right_val)
        return helper({'a': k, 'b': k, 'c': k}, 0, len(s) - 1)

Sliding window

class Solution:
    def takeCharacters(self, s: str, k: int) -> int:
        s_cnt = collections.Counter(s)
        limits = {c: s_cnt[c] - k for c in 'abc'}
        if any(val < 0 for val in limits.values()):
            return -1
        left = 0
        cur_cnt = {'a': 0, 'b': 0, 'c': 0}
        res = len(s) + 1
        for right in range(len(s)):
            cur_cnt[s[right]] += 1
            while cur_cnt[s[right]] > limits[s[right]]:
                cur_cnt[s[left]] -= 1
                left += 1
            res = min(res, len(s) - (right - left + 1))
        return res