Problem statement

https://leetcode.com/problems/smallest-k-length-subsequence-with-occurrences-of-a-letter/

Solution

As mentioned in some other posts, this problem is more difficult version of problem 0316 Remove Duplicate Letters. The idea is try to construct our answer in greedy way, each time deciding if we can improve our answer, which we keep in stack or not. To do it efficiently we need array suff, which for example for s = leetcode and letter = e will be equal to [3, 3, 2, 1, 1, 1, 1, 1]: it means, that for index 0 we have 3 more letters starting from this index which is equal to e, for index 5 we have 1 more letters starting from this index which is equal to e.

  1. I added dummy symbol ! to stack to make sure it is never empty.
  2. r will mean how many elements l we still need to put in our stack.

Now, we traverse our string s and we want to decide if we can remove some elements from the end of stack:

  1. We need stack[-1] > c condition: that is if we want to add new element c we want our answer to decrease.
  2. len(stack) + n - i > k + 1, it means that we still have enough letter ahead to be able to reach k elements in our answer.
  3. stack[-1] != l or r < suff[i] condition: first one means that last element of stack is not letter l: if we remove it from stack, number of letters l in stack will not change, so we can safely do it. Or if r < suff[i] means, that last element in stack is l, but if we remove it we still have enough letters l ahead.
  4. If we decide to pop element, we update r.

Now, when we add elements to stack? We need two conditions:

  1. len(stack) < k + 1 (+1 here because we use dummy !), because obviously answer can not be longer than k + 1.
  2. len(stack) < k + 1 - r + (c == l) - this is another crucuial condition you should not miss: it means that you still have enough spaces in you stack to fill it with letters l. If we do not use it, we can have something like [a a a] in stack with letter l = "b" and we just do not have enough space in our stack to put letters l.
  3. If we decide to add element, we update r.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def smallestSubsequence(self, s, k, l, r):
        n, stack = len(s), ["!"]
        suff = list(accumulate([c == l for c in s][::-1]))[::-1]
        
        for i, c in enumerate(s): 
            while stack[-1] > c and len(stack) + n - i > k + 1 and (stack[-1] != l or r < suff[i]):
                r += stack.pop() == l
            if len(stack) < min(k, k - r + (c==l)) + 1:
                stack += [c]
                r -= (c == l)
        
        return "".join(stack[1:])