Smallest K-Length Subsequence With Occurrences of a Letter — Hard Problem & Solution

Return the lexicographically smallest subsequence of s that has length exactly k and contains the character letter at least repetition times.

Difficulty: Hard
Topics: Strings, Greedy, Stack, Monotonic Stack
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Return the lexicographically smallest subsequence of s that has length exactly k and contains the character letter at least repetition times. The input guarantees such a subsequence exists.

Example 1

Input: s = "codekairo", k = 3, letter = "o", repetition = 2
Output: coo
Explanation: Both `o`s are required, so only the third character is free — and `c` beats every letter between them.

Example 2

Input: s = "leetcode", k = 4, letter = "e", repetition = 2
Output: ecde

Example 3

Input: s = "leet", k = 3, letter = "e", repetition = 1
Output: eet

Constraints

1 <= repetition <= k <= s.length <= 5 * 10^4
s consists of lowercase English letters.
letter is a lowercase English letter, and appears in s at least repetition times.

How to solve Smallest K-Length Subsequence With Occurrences of a Letter

Run the standard greedy monotonic stack for the smallest length-k subsequence, and add two feasibility guards that keep the letter quota reachable at every step.

Approach

Count the total occurrences of letter; keep remaining = how many are at or after the current index, and inStack = how many are on the stack.
For each character c: pop the stack top while it is greater than c, and enough characters remain to still reach length k, and — if the top is letter — dropping it would still leave inStack - 1 + remaining >= repetition.
Push c when the stack is shorter than k. A letter always pushes. A non-letter pushes only if k - stack.length > repetition - inStack, i.e. there is still a free slot after reserving space for the outstanding quota.
Decrement remaining after processing an occurrence of letter.

Why it works

The plain greedy is correct because replacing a larger earlier character with a smaller later one always improves the result at the first position where they differ. The two guards are what make it correct under a constraint: the pop guard refuses to discard a letter the quota still needs, and the push guard refuses to spend a slot that the quota has already claimed. Both are checked against the counts rather than by lookahead, which keeps the whole thing one linear pass.

Complexity

Time — O(n)
Space — O(k)

Pitfalls

Popping a letter without checking the quota can make the target unreachable, with no way to recover later in the pass.
The push guard is a strict >: the slot being filled must not be one the quota needs.
remaining must count the occurrence at the current index while it is being processed, and drop only afterwards.

Reference solution

Python

def smallestSubsequence(s: str, k: int, letter: str, repetition: int) -> str:
    n = len(s)
    remaining = s.count(letter)
    stack = []
    in_stack = 0
    for i, c in enumerate(s):
        while (stack and stack[-1] > c and len(stack) + (n - i) > k
               and (stack[-1] != letter or in_stack - 1 + remaining >= repetition)):
            if stack[-1] == letter:
                in_stack -= 1
            stack.pop()
        if len(stack) < k:
            if c == letter:
                stack.append(c)
                in_stack += 1
            elif k - len(stack) > repetition - in_stack:
                stack.append(c)
        if c == letter:
            remaining -= 1
    return "".join(stack)

JavaScript

var smallestSubsequence = function(s, k, letter, repetition) {
    var n = s.length, i;
    var remaining = 0;
    for (i = 0; i < n; i++) if (s.charAt(i) === letter) remaining++;
    var stack = [], inStack = 0;
    for (i = 0; i < n; i++) {
        var c = s.charAt(i);
        while (stack.length > 0 && stack[stack.length - 1] > c
            && stack.length + (n - i) > k
            && (stack[stack.length - 1] !== letter || inStack - 1 + remaining >= repetition)) {
            if (stack[stack.length - 1] === letter) inStack--;
            stack.pop();
        }
        if (stack.length < k) {
            if (c === letter) { stack.push(c); inStack++; }
            else if (k - stack.length > repetition - inStack) stack.push(c);
        }
        if (c === letter) remaining--;
    }
    return stack.join("");
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue