Smallest K-Length Subsequence With Occurrences of a Letter - Solution & Explanation

Problem Overview: Given a string s, you must build the lexicographically smallest subsequence of length k that contains at least repetition occurrences of a specific letter. You can remove characters but must preserve order. The challenge is balancing lexicographic minimality with the constraint that enough required letters remain.

Approach 1: Greedy Monotonic Stack (O(n) time, O(k) space)

This approach uses a monotonic stack to build the subsequence while scanning the string once. When processing each character, you try to maintain the smallest lexicographic order by popping larger characters from the stack if enough characters remain to still reach length k. At the same time, you must track how many required letter characters are still available in the remaining suffix and ensure the stack keeps enough of them to satisfy repetition. The algorithm keeps counters for remaining letters and required letters inside the stack, preventing pops that would make the constraint impossible to satisfy.

Greedy removal combined with the stack ordering ensures the resulting subsequence is minimal. Because each character is pushed and popped at most once, the runtime is linear. This pattern appears frequently in greedy string construction problems and is closely related to monotonic stack techniques used for lexicographically smallest subsequences.

Approach 2: Priority Queue (Min-Heap) Selection (O(n log n) time, O(n) space)

A more direct strategy uses a min-heap to always select the smallest possible next character within the valid index window. For each subsequence position, you consider the range of characters that still allows enough remaining positions to complete the subsequence and satisfy the required number of letter occurrences. The heap helps quickly pick the smallest candidate character. After selecting a character, you move the starting index forward and update how many required letters are still needed.

This approach mirrors the classic "smallest subsequence with constraints" strategy but relies on heap operations instead of a stack. It is easier to reason about window selection but costs O(log n) per insertion or extraction. The method is useful when implementing selection-based greedy logic or when practicing heap-driven solutions in string problems.

Recommended for interviews: The Greedy Monotonic Stack solution is what interviewers typically expect. It demonstrates control over lexicographic ordering, constraint tracking, and amortized stack operations. The heap solution shows correct reasoning but is less optimal. Explaining both signals strong problem-solving depth: brute reasoning about subsequences followed by an optimal greedy structure.