Smallest K-Length Subsequence With Occurrences of a Letter

Hard
1038.

Smallest K-Length Subsequence With Occurrences of a Letter

Smallest K-Length Subsequence With Occurrences of a Letter is a hard coding problem on strings, greedy and stack, asked in Amazon, Google and Microsoft interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number} k
 * @param {string} letter
 * @param {number} repetition
 * @return {string}
 */
var smallestSubsequence = function(s, k, letter, repetition) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Smallest K-Length Subsequence With Occurrences of a Letter Solution

Smallest K-Length Subsequence With Occurrences of a Letter solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Smallest K-Length Subsequence With Occurrences of a Letter is a hard coding problem on strings, greedy and stack, asked in Amazon, Google and Microsoft interviews.

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.

Hints for Smallest K-Length Subsequence With Occurrences of a Letter

  1. Hint 1

    Without the letter requirement this is the classic "smallest subsequence of length k" monotonic-stack problem.

  2. Hint 2

    Two extra guards are needed: never pop a letter if the ones left cannot make up the quota, and never push a non-letter if it would leave too few slots for the quota.

  3. Hint 3

    Track how many letters are still ahead in s and how many are already on the stack.

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

  1. 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.
  2. 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.
  3. 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.
  4. 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)

Java

public static String smallestSubsequence(String s, int k, String letter, int repetition) {
    int n = s.length();
    char target = letter.charAt(0);
    int remaining = 0;
    for (int i = 0; i < n; i++) {
        if (s.charAt(i) == target) remaining++;
    }
    char[] stack = new char[n];
    int top = 0, inStack = 0;
    for (int i = 0; i < n; i++) {
        char c = s.charAt(i);
        while (top > 0 && stack[top - 1] > c && top + (n - i) > k
                && (stack[top - 1] != target || inStack - 1 + remaining >= repetition)) {
            if (stack[top - 1] == target) inStack--;
            top--;
        }
        if (top < k) {
            if (c == target) {
                stack[top++] = c;
                inStack++;
            } else if (k - top > repetition - inStack) {
                stack[top++] = c;
            }
        }
        if (c == target) remaining--;
    }
    return new String(stack, 0, top);
}

C++

string smallestSubsequence(string s, int k, string letter, int repetition) {
    int n = (int) s.size();
    char target = letter[0];
    int remaining = 0;
    for (char c : s) {
        if (c == target) remaining++;
    }
    string stk;
    int inStack = 0;
    for (int i = 0; i < n; i++) {
        char c = s[i];
        while (!stk.empty() && stk.back() > c && (int) stk.size() + (n - i) > k
               && (stk.back() != target || inStack - 1 + remaining >= repetition)) {
            if (stk.back() == target) inStack--;
            stk.pop_back();
        }
        if ((int) stk.size() < k) {
            if (c == target) {
                stk += c;
                inStack++;
            } else if (k - (int) stk.size() > repetition - inStack) {
                stk += c;
            }
        }
        if (c == target) remaining--;
    }
    return stk;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Greedy Algorithms