2030. Smallest K Length Subsequence With Occurrences of a Letter

Problem Description

Given a string s, we need to find the lexicographically smallest subsequence of length k that contains the character letter exactly repetition number of times.

** Constraints:**

• 1 <= k <= s.length <= 1000
• 1 <= repetition <= k <= 1000
• 1 <= letter.length == 1
• s and letter consist of only lowercase English letters.

Example

Let's walk through an example:

Input: s = "leetcode", k = 4, letter = 'e', repetition = 2

Output: "eecd"

Explanation: The lexicographically smallest subsequence that meets the requirement is "eecd" with 2 'e' characters.

Approach

The main idea of the solution is to use a stack data structure to maintain the desired subsequence characters. We can iterate through the input string, and for each character, we try to keep the stack in lexicographically increasing order if the remaining characters and constraints allow us to do so.

There are three cases we need to cover:

1. If the character is equal to letter, push it onto the stack and decrement the required count.
2. If the character is not equal to letter and we can still push more characters onto the stack to meet the length of k, push the character.
3. If the character is equal to letter but our stack is already full (stack.size() == k), don't push it to the stack.

Finally, we convert the stack into a string and return it as the answer.

ASCII Illustration

Suppose s = "leetcode", k = 4, letter = 'e', repetition = 2

Initial state:

• stack = []
• required = 2
• nLetters = 3 (number of 'letter' in the input string)

Processing each character of the input string:

s[0]: 'l'

• stack = ['l']

s[1]: 'e'

• stack = ['e'] (pop 'l' since we need to add 'e')

s[2]: 'e'

• stack = ['e', 'e']

s[3]: 't'

• Ignore (since we've already added the required number of 'e')

s[4]: 'c'

• stack = ['e', 'e', 'c']

s[5]: 'o'

• Ignore (since adding 'o' would make the sequence lexographically larger)

s[6]: 'd'

• stack = ['e', 'e', 'c', 'd'] (our final subsequence)

s[7]: 'e'

• Ignore (already added the required number of 'e')

Final answer: "eecd".

Solution in Python

1
2python
3class Solution:
4    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:
5        ans = ""
6        stack = []
7        required = repetition
8        nLetters = s.count(letter)
9
10        for i in range(len(s)):
11            c = s[i]
12            while stack and stack[-1] > c and len(stack) + len(s) - i - 1 >= k and (stack[-1] != letter or nLetters > required):
13                popped = stack.pop()
14                if popped == letter:
15                    required += 1
16            if len(stack) < k:
17                if c == letter:
18                    stack.append(c)
19                    required -= 1
20                elif k > len(stack) + required:
21                    stack.append(c)
22            if c == letter:
23                nLetters -= 1
24
25        return "".join(stack)

Solution in Java

1
2java
3import java.util.*;
4
5class Solution {
6    public String smallestSubsequence(String s, int k, char letter, int repetition) {
7        String ans = "";
8        List<Character> stack = new ArrayList<>();
9        int required = repetition;
10        int nLetters = (int) s.chars().filter(c -> c == letter).count();
11
12        for (int i = 0; i < s.length(); ++i) {
13            char c = s.charAt(i);
14            while (!stack.isEmpty() && stack.get(stack.size() - 1) > c && stack.size() + s.length() - i - 1 >= k && (stack.get(stack.size() - 1) != letter || nLetters > required)) {
15                char popped = stack.remove(stack.size() - 1);
16                if (popped == letter)
17                    ++required;
18            }
19            if (stack.size() < k)
20                if (c == letter) {
21                    stack.add(c);
22                    --required;
23                } else if (k > stack.size() + required) {
24                    stack.add(c);
25                }
26            if (c == letter)
27                --nLetters;
28        }
29
30        for (char c : stack)
31            ans += c;
32
33        return ans;
34    }
35}

Solution in JavaScript

1
2javascript
3class Solution {
4    smallestSubsequence(s, k, letter, repetition) {
5        let ans = "";
6        let stack = [];
7        let required = repetition;
8        let nLetters = s.split(letter).length - 1;
9
10        for (let i = 0; i < s.length; ++i) {
11            const c = s[i];
12            while (stack.length > 0 && stack[stack.length - 1] > c && stack.length + s.length - i - 1 >= k && (stack[stack.length - 1] != letter || nLetters > required)) {
13                const popped = stack.pop();
14                if (popped == letter)
15                    ++required;
16            }
17            if (stack.length < k)
18                if (c == letter) {
19                    stack.push(c);
20                    --required;
21                } else if (k > stack.length + required) {
22                    stack.push(c);
23                }
24            if (c == letter)
25                --nLetters;
26        }
27
28        return stack.join("");
29    }
30}

Solution in C++

1
2cpp
3#include <vector>
4#include <string>
5#include <algorithm>
6
7class Solution {
8 public:
9  std::string smallestSubsequence(std::string s, int k, char letter, int repetition) {
10    std::string ans;
11    std::vector<char> stack;
12    int required = repetition;
13    int nLetters = count(begin(s), end(s), letter);
14
15    for (int i = 0; i < s.length(); ++i) {
16      const char c = s[i];
17      while (!stack.empty() && stack.back() > c &&
18             stack.size() + s.length() - i - 1 >= k &&
19             (stack.back() != letter || nLetters > required)) {
20        const char popped = stack.back();
21        stack.pop_back();
22        if (popped == letter)
23          ++required;
24      }
25      if (stack.size() < k)
26        if (c == letter) {
27          stack.push_back(c);
28          --required;
29        } else if (k > stack.size() + required) {
30          stack.push_back(c);
31        }
32      if (c == letter)
33        --nLetters;
34    }
35
36    for (const char c : stack)
37      ans += c;
38
39    return ans;
40  }
41};

Solution in C#

1
2csharp
3using System;
4using System.Collections.Generic;
5
6public class Solution {
7    public string SmallestSubsequence(string s, int k, char letter, int repetition) {
8        string ans = "";
9        List<char> stack = new List<char>();
10        int required = repetition;
11        int nLetters = s.Length - s.Replace(letter.ToString(), "").Length;
12
13        for (int i = 0; i < s.Length; ++i) {
14            char c = s[i];
15            while (stack.Count > 0 && stack[^1] > c && stack.Count + s.Length - i - 1 >= k && (stack[^1] != letter || nLetters > required)) {
16                char popped = stack[stack.Count - 1];
17                stack.RemoveAt(stack.Count - 1);
18                if (popped == letter)
19                    ++required;
20            }
21            if (stack.Count < k)
22                if (c == letter) {
23                    stack.Add(c);
24                    --required;
25                } else if (k > stack.Count + required) {
26                    stack.Add(c);
27                }
28            if (c == letter)
29                --nLetters;
30        }
31
32        foreach (char c in stack)
33            ans += c;
34
35        return ans;
36    }
37}

Explanation of the Solutions

In this problem, we need to find the smallest subsequence of length k containing the character letter exactly repetition times. We use a stack to push the characters of the input string while maintaining the lexicographically smallest subsequence.

Let's discuss the intuition and code implementation of each solution language.

Python Solution

The python solution defines a class Solution with a method smallestSubsequence that takes three parameters: s, k, letter, and repetition.

1. Initialize an empty stack (stack = []), a variable required equal to repetition, and a variable nLetters equal to the count of occurrences of the letter in the input string s.
2. Iterate through the input string using the loop for i in range(len(s)). At each iteration, store the current character in variable c, and handle three cases mentioned before.
3. If the character is higher in the lexicographical order, then pop it from the stack to maintain the lexicographically smallest subsequence.
4. If the character is equal to the letter and the stack size is less than k, push c to the stack and decrease the required count.
5. If the character is different from the letter and the stack size plus required is less than k, push c to the stack.
6. If the character is equal to the letter, decrease the nLetters count.
7. Join the stack to form a string and return it as the answer.

Java Solution

The Java solution is similar to the Python solution but uses a List to hold the subsequence characters instead of a list as in the Python solution. Also, instead of using the count method of the String class, we use a lambda expression and a stream filter to count the occurrences of the letter.

JavaScript Solution

In the JavaScript solution, we use the method split to count the occurrences of the letter in the input string s. The rest of the code follows the same steps as in the Python solution, but we use methods push and pop to add and remove elements from the stack, respectively.

C++ Solution

The C++ solution uses a vector of char to hold the subsequence characters. It uses the count method of the algorithm library to count the occurrences of the letter in the input string s. The code follows the same steps as in the Python solution, and the stack is a vector of char.

C# Solution

The C# solution uses a List to hold the subsequence characters and a lambda expression to count the occurrences of the letter in the input string s. It follows the same steps as in the Python solution, but using the methods Add and RemoveAt to add and remove elements from the stack, respectively.