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
Which of the following shows the order of node visit in a Breadth-first Search?
Which two pointer techniques do you use to check if a string is a palindrome?
Solution Implementation
How many times is a tree node visited in a depth first search?
Which of these properties could exist for a graph but not a tree?
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
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.