You are given a string s, an integer k, a letter letter, and an integer repetition.
Return the lexicographically smallest subsequence of s of length k that has the letter letter appear at least repetition times. The test cases are generated so that the letter appears in s at least repetition times.
A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.
A string a is lexicographically smaller than a string b if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b.
Example 1:
Input: s = "leet", k = 3, letter = "e", repetition = 1 Output: "eet" Explanation: There are four subsequences of length 3 that have the letter 'e' appear at least 1 time: - "lee" (from "leet") - "let" (from "leet") - "let" (from "leet") - "eet" (from "leet") The lexicographically smallest subsequence among them is "eet".
Example 2:
Input: s = "leetcode", k = 4, letter = "e", repetition = 2 Output: "ecde" Explanation: "ecde" is the lexicographically smallest subsequence of length 4 that has the letter "e" appear at least 2 times.
Example 3:
Input: s = "bb", k = 2, letter = "b", repetition = 2 Output: "bb" Explanation: "bb" is the only subsequence of length 2 that has the letter "b" appear at least 2 times.
Constraints:
1 <= repetition <= k <= s.length <= 5 * 104s consists of lowercase English letters.letter is a lowercase English letter, and appears in s at least repetition times.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.
The main idea of this approach is to use a stack to construct the subsequence while iterating over the string. You try to maintain a lexicographical order by always pushing the smallest possible character onto the stack. Restrictions are maintained by ensuring enough repetitions of the required letter remain possible, and the overall remaining length constraint is handled by potentially popping from the stack.
The function uses a stack-based approach to gradually build the smallest lexicographical subsequence of a desired length. In each iteration, character decisions rely on potential replacements that wouldn't violate sequence constraints, hence sometimes popping the stack. The solution takes care to always maintain clarity on meeting the required repetitions of the designated letter.
Python
JavaScript
Time Complexity: O(n) because each character is processed no more than twice.
Space Complexity: O(k) for the stack.
A priority queue approach might be affected by overhead due to heap operations. However, conceptually, you enqueue characters while maintaining constraints, allowing an efficient rebuilding of potential subsequences based on priority. Managing repetitions and overall sequence constraints adds complexity.
This C++ solution employs a priority queue to manage a potential subsequence by continuously inserting characters based on their order. Capturing repetitions involves strategic enqueuing, and decisions incorporate character comparison and constraints to ensure valid subsequences.
Time Complexity: O(n log n) primarily due to the priority queue operations.
Space Complexity: O(n) for the priority queue and other string constructions.
| Approach | Complexity |
|---|---|
| Greedy Stack Approach | Time Complexity: O(n) because each character is processed no more than twice. |
| Priority Queue (Min-Heap) Approach | Time Complexity: O(n log n) primarily due to the priority queue operations. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Monotonic Stack | O(n) | O(k) | Best general solution when building lexicographically smallest subsequences with constraints |
| Priority Queue (Min-Heap) | O(n log n) | O(n) | Useful when selecting the smallest valid character from dynamic ranges |
LeetCode 2030. Smallest K-Length Subsequence With Occurrences of a Letter • Happy Coding • 4,313 views views
Watch 5 more video solutions →Practice Smallest K-Length Subsequence With Occurrences of a Letter with our built-in code editor and test cases.
Practice on FleetCode