LC-2516 Medium LeetCode

2516. Take K of Each Character From Left and Right

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 52% Topics: Hash Table, String, Sliding Window

Reading material

Arrays & Hashing 12 min Strings 12 min Sliding Window 11 min

Reference solution (spoiler · python)

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

# sliding window, two pointers
class Solution(object):
    def takeCharacters(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        cnt = [0]*3
        for c in s:
            cnt[ord(c)-ord('a')] += 1
        if min(cnt) < k:
            return -1
        result = left = 0
        for right in xrange(len(s)):
            cnt[ord(s[right])-ord('a')] -= 1
            while cnt[ord(s[right])-ord('a')] < k:
                cnt[ord(s[left])-ord('a')] += 1
                left += 1
            result = max(result, right-left+1)
        return len(s)-result

Solution from kamyu104/LeetCode-Solutions · MIT