Smallest K-Length Subsequence With Occurrences of a Letter

Use a monotonic stack to build the smallest subsequence while ensuring the required letter occurs enough times. Pop larger characters if space allows and the remaining letters can satisfy repetition. Push each character only if it maintains both length and repetition constraints, scanning s once for an optimal O(n) solution.

Problem Statement

Given a string s, an integer k, a target letter, and a repetition count, return the lexicographically smallest subsequence of s of length k where the target letter appears at least repetition times. The string s contains at least repetition occurrences of the target letter.

A subsequence is formed by deleting zero or more characters from s without changing the order of the remaining characters. Your task is to select characters strategically using a stack-based method to ensure the smallest lexicographical order while satisfying length and letter repetition requirements.

Examples

Example 1

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

Output: "eet"

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"

"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"

"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 * 104
• s consists of lowercase English letters.
• letter is a lowercase English letter, and appears in s at least repetition times.

Solution Approach

Track remaining letters and stack state

Count how many target letters remain in s. Use a stack to maintain the current subsequence. For each character, decide whether to pop from the stack if the current character is smaller and popping won't prevent reaching k length or the required repetitions.

Greedy insertion

Push the current character onto the stack if it fits within the remaining length and repetition constraints. Always ensure that the number of target letters left to process plus those in the stack can satisfy the repetition requirement.

Finalize the subsequence

After processing all characters, truncate or remove extra characters from the end of the stack if it exceeds length k. Return the stack content as the lexicographically smallest subsequence that meets the repetition condition.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each character is pushed and popped at most once. Space complexity is O(k) for the stack used to store the subsequence.

What Interviewers Usually Probe

• Do you understand how to enforce letter repetition constraints while maintaining lexicographic order?
• Are you tracking the remaining letters correctly to decide when to pop from the stack?
• Can you justify why a monotonic stack guarantees the smallest subsequence in this problem?

Common Pitfalls or Variants

Common pitfalls

• Forgetting to ensure that popping a character does not reduce the available target letters below repetition.
• Not considering the total remaining letters when deciding to push a character.
• Trimming the stack incorrectly at the end, leading to length or repetition violations.

Follow-up variants

• Find the lexicographically largest k-length subsequence with a minimum letter occurrence.
• Handle multiple letters with individual repetition constraints using a similar stack strategy.
• Extend to k-length subsequences where the target letter must appear exactly repetition times instead of at least.

FAQ

What pattern does this problem use?

This problem is based on stack-based state management and monotonic stack logic to enforce lexicographical order and repetition constraints.

Can the stack approach handle large strings efficiently?

Yes, the algorithm processes each character at most twice, resulting in O(n) time complexity even for strings up to length 5*10^4.

How do I ensure the target letter appears at least repetition times?

Track remaining occurrences of the target letter while iterating, and only pop or push characters if doing so preserves enough letters to meet the repetition requirement.

Is it necessary to pop characters that are not the target letter?

Yes, you may pop non-target letters if the current character is smaller and popping won't violate length or repetition constraints to achieve the smallest subsequence.

Does this method always produce the lexicographically smallest subsequence?

Yes, by greedily maintaining a monotonic stack and considering remaining letters, the stack ensures the final subsequence is the smallest possible.