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:
- If the character is equal to
letter
, push it onto the stack and decrement therequired
count. - If the character is not equal to
letter
and we can still push more characters onto the stack to meet the length ofk
, push the character. - 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
.
- Initialize an empty stack (
stack = []
), a variablerequired
equal torepetition
, and a variablenLetters
equal to the count of occurrences of theletter
in the input strings
. - Iterate through the input string using the loop
for i in range(len(s))
. At each iteration, store the current character in variablec
, and handle three cases mentioned before. - If the character is higher in the lexicographical order, then pop it from the stack to maintain the lexicographically smallest subsequence.
- 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.
- If the character is different from the letter and the stack size plus required is less than k, push c to the stack.
- If the character is equal to the letter, decrease the nLetters count.
- 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
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
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.