Skip to content

Find Largest Subsequence of K Digits

Level: L3-L5 Topics: Greedy, Monotonic Stack, Arrays

Problem Statement

Given a sequence S of N digits (as a string or array), find the subsequence of exactly K digits that forms the largest possible number.

A subsequence maintains the relative order of elements from the original sequence but does not need to be contiguous.

Background & Constraints

  • 1 <= K <= N <= 1,000,000
  • Each element is a single digit (0-9).
  • The result should preserve the original relative order of digits.
  • Among all subsequences of length K, return the one that is lexicographically largest (i.e., forms the largest number).
  • Leading zeros are allowed in the subsequence if that is what the algorithm produces.

Examples

Example 1:

S = "4902", K = 2
Answer: "92"
Explanation: All subsequences of length 2: 49, 40, 42, 90, 92, 02. Largest is 92.

Example 2:

S = "7138294", K = 3
Answer: "894"
Explanation: Indices: 7(0) 1(1) 3(2) 8(3) 2(4) 9(5) 4(6).
- For K=3, the first picked digit must come from indices 0..N-K = 0..4, i.e. [7,1,3,8,2].
  Largest is 8 at index 3.
- For the second digit, search indices 4..N-(K-1) = 4..5, i.e. [2,9].
  Largest is 9 at index 5.
- For the third digit, only index 6 remains: 4.
- Result: "894".

Example 3:

S = "111", K = 2
Answer: "11"

Example 4:

S = "54321", K = 3
Answer: "543"

Hints & Common Pitfalls

  • Greedy / monotonic stack approach: Maintain a stack (or result array). Iterate through the digits. While the current digit is larger than the top of the stack AND you still have enough digits remaining to fill K positions, pop the stack. Then push the current digit. At the end, truncate to K digits.

  • Key insight: You are allowed to "remove" exactly N - K digits. The greedy strategy removes the smallest possible digits from left to right. Whenever you see a digit larger than the previous one, the previous one is a candidate for removal.

  • Time complexity: The stack approach is O(N) since each digit is pushed and popped at most once.

  • Common mistake: Not checking if there are enough remaining digits before popping. If you pop too aggressively, you might not have enough digits left to fill K positions.

  • Another mistake: Forgetting to truncate the result. If no pops happen (e.g., sequence is non-increasing), the stack will contain all N digits and you need to take only the first K.

Follow-Up Questions

  1. Solve for all K in O(N) total time: Can you precompute the answer for every possible value of K (from 1 to N) in O(N) total time? The monotonic stack built during a single pass contains enough information. Think about how the stack state at the end relates to different values of K.

  2. Smallest subsequence: How would you modify the algorithm to find the subsequence of K digits forming the smallest number? What changes in the stack comparison?

  3. Two sequences: Given two sequences S1 and S2 of lengths N1 and N2, pick K1 digits from S1 and K2 digits from S2 (where K1+K2 = K) such that merging them (maintaining relative order within each source) produces the largest possible number. How do you choose K1 and K2, and how do you merge optimally?