Problem

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.

Examples

Example 1:

$$ \begin{array}{cccc} l & \colorbox{green}{e} & \colorbox{green}{e} & \colorbox{green}{t} \\ \end{array} $$

1
2
3
4
5
6
7
8

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 "**lee**t")
- "let" (from "**le**e**t**")
- "let" (from "**l**e**et**")
- "eet" (from "l**eet**")
The lexicographically smallest subsequence among them is "eet".

Example 2:

$$ \begin{array}{cccccccc} l & e & \colorbox{green}{e} & t & \colorbox{green}{c} & o & \colorbox{green}{d} & \colorbox{green}{e} \\ \end{array} $$

1
2
3

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: $$ \begin{array}{cc} \colorbox{green}{b} & \colorbox{green}{b} \\ \end{array} $$

1
2
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.

Solution

Method 1 - Using Monotonic Increasing stack

We can use monotonically increasing stack to maintain elements in increasing order in the stack to ensure the smallest lexicographical sequence is formed.

  1. While iterating through the string, if the current character is smaller than the character at the top of the stack and it is possible to maintain the length of the subsequence (k) and required occurrences of the letter, we pop the top of the stack.
  2. This way, the characters left in the stack are in increasing order, ensuring the sequence remains lexicographically smallest.

Here is the approach:

  1. Use Monotonic Stack:
    • Traverse the string s and use a stack to build the resulting subsequence while maintaining the lexicographical order.
    • Ensure that the resulting subsequence satisfies the constraints:
      • Length should be k.
      • It should contain letter at least repetition times.
  2. Keep track of necessary elements:
    • Use counters to keep track of the remaining necessary occurrences of letter.
  3. Greedily build the stack:
    • If the current character can replace the top of the stack to form a smaller lexicographical order while maintaining the constraints, do so.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

class Solution {
    public String smallestSubsequence(String s, int k, char letter, int repetition) {
        int len = s.length();
        int count = 0;
        for (char ch : s.toCharArray()) {
            if (ch == letter) {
                count++;
            }
        }
        
        Deque<Character> stack = new ArrayDeque<>();
        int letterCount = 0;  // Number of `letter` selected
        int letterRemain = count;

        for (char ch : s.toCharArray()) {
            while (!stack.isEmpty() && stack.peekLast() > ch 
                && stack.size() + len - 1 - stack.size() >= k 
                && (stack.size() - letterCount + repetition > k || k - stack.size() < repetition - letterCount)) {
                char removed = stack.removeLast();
                if (removed == letter) {
                    letterCount--;
                }
            }

            if (stack.size() < k) {
                if (ch == letter) {
                    stack.addLast(ch);
                    letterCount++;
                } else if (stack.size() + (letterRemain - repetition + letterCount) >= repetition) {
                    stack.addLast(ch);
                }
            }

            if (ch == letter) {
                letterRemain--;
            }
        }

        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.removeFirst());
        }
        return sb.toString();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution:
    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:
        n = len(s)
        remain = s.count(letter)
        stack = deque()
        count = 0  # Number of `letter` selected
        available = remain

        for ch in s:
            while (stack and stack[-1] > ch 
                and len(stack) + n - len(stack) - 1 >= k 
                and (len(stack) - count + repetition > k or k - len(stack) < repetition - count)):
                if stack[-1] == letter:
                    count -= 1
                stack.pop()
                available += 1
            
            if ch == letter:
                stack.append(ch)
                count += 1
            elif len(stack) < k:
                if len(stack) + (available - repetition + count) >= repetition:
                    stack.append(ch)
                    available -= 1
            else:
                available -= 1

        while len(stack) > k:
            stack.pop()

        ans = ''.join(stack).lstrip('0')
        return ans if ans else "0"

Complexity

  • ⏰ Time complexity: O(n), as the algorithm processes each character in the string once and performs operations on the stack.
  • 🧺 Space complexity: O(k), due to storing up to k characters in the stack.