# 2030. Smallest K-Length Subsequence With Occurrences of a Letter      • Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 class Solution { public: string smallestSubsequence(string s, int k, char letter, int repetition) { string ans; vector stack; int required = repetition; int nLetters = count(begin(s), end(s), letter); for (int i = 0; i < s.length(); ++i) { const char c = s[i]; while (!stack.empty() && stack.back() > c && stack.size() + s.length() - i - 1 >= k && (stack.back() != letter || nLetters > required)) { const char popped = stack.back(); stack.pop_back(); if (popped == letter) ++required; } if (stack.size() < k) if (c == letter) { stack.push_back(c); --required; } else if (k > stack.size() + required) { stack.push_back(c); } if (c == letter) --nLetters; } for (const char c : stack) ans += c; return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public String smallestSubsequence(String s, int k, char letter, int repetition) { StringBuilder sb = new StringBuilder(); Deque stack = new ArrayDeque<>(); int required = repetition; int nLetters = (int) s.chars().filter(c -> c == letter).count(); for (int i = 0; i < s.length(); ++i) { final char c = s.charAt(i); while (!stack.isEmpty() && stack.peek() > c && stack.size() + s.length() - i - 1 >= k && (stack.peek() != letter || nLetters > required)) if (stack.pop() == letter) ++required; if (stack.size() < k) if (c == letter) { stack.push(c); --required; } else if (k - stack.size() > required) { stack.push(c); } if (c == letter) --nLetters; } for (final char c : stack) sb.append(c); return sb.reverse().toString(); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution: def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str: stack = [] # running string required = repetition nLetters = s.count(letter) for i, c in enumerate(s): # Make sure the length is sufficient: # len(stack) := length of running string # len(s) - i := length of remain chars # -1 := we're going to pop a char while stack and stack[-1] > c \ and len(stack) + len(s) - i - 1 >= k \ and (stack[-1] != letter or nLetters > required): if stack.pop() == letter: required += 1 if len(stack) < k: if c == letter: stack.append(c) required -= 1 elif k - len(stack) > required: stack.append(c) if c == letter: nLetters -= 1 return ''.join(stack)