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.
- 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^4s 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
Hint 1
Without the
letterrequirement this is the classic "smallest subsequence of length k" monotonic-stack problem.Hint 2
Two extra guards are needed: never pop a
letterif the ones left cannot make up the quota, and never push a non-letter if it would leave too few slots for the quota.Hint 3
Track how many
letters are still ahead insand 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
- Count the total occurrences of
letter; keepremaining= how many are at or after the current index, andinStack= how many are on the stack. - For each character
c: pop the stack top while it is greater thanc, and enough characters remain to still reach lengthk, and — if the top isletter— dropping it would still leaveinStack - 1 + remaining >= repetition. - Push
cwhen the stack is shorter thank. Aletteralways pushes. A non-letter pushes only ifk - stack.length > repetition - inStack, i.e. there is still a free slot after reserving space for the outstanding quota. - Decrement
remainingafter processing an occurrence ofletter.
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
letterwithout 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. remainingmust 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