Take K of Each Character From Left and Right — LeetCode 2516 Python Solution

The problem

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.

Example

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.

Python solution

class Solution:
    def takeCharacters(self, s: str, k: int) -> int:
        cnt = Counter(s)
        if any(cnt[c] < k for c in "abc"):
            return -1
        mx = j = 0
        for i, c in enumerate(s):
            cnt[c] -= 1
            while cnt[c] < k:
                cnt[s[j]] += 1
                j += 1
            mx = max(mx, i - j + 1)
        return len(s) - mx

Complexity

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 2516. Take K of Each Character From Left and Right is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Related problems