2030. Smallest K-Length Subsequence With Occurrences of a Letter LeetCode Solution
In this guide, you will get 2030. Smallest K-Length Subsequence With Occurrences of a Letter LeetCode Solution with the best time and space complexity. The solution to Smallest K-Length Subsequence With Occurrences of a Letter problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Smallest K-Length Subsequence With Occurrences of a Letter
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.
Example 1:
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 “leet”)
– “let” (from “leet”)
– “let” (from “leet”)
– “eet” (from “leet”)
The lexicographically smallest subsequence among them is “eet”.
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:
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.
Constraints:
1 <= repetition <= k <= s.length <= 5 * 104
s consists of lowercase English letters.
letter is a lowercase English letter, and appears in s at least repetition times.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
2030. Smallest K-Length Subsequence With Occurrences of a Letter LeetCode Solution in C++
class Solution {
public:
string smallestSubsequence(string s, int k, char letter, int repetition) {
string ans;
vector<char> stack;
int required = repetition;
int nLetters = ranges::count(s, letter);
for (int i = 0; i < s.length(); ++i) {
const char c = s[i];
while (!stack.empty() && stack.back() > c &&
stack.size() + s.length() - i - 1 >= k &&
(stack.back() != letter || nLetters > required)) {
const char popped = stack.back();
stack.pop_back();
if (popped == letter)
++required;
}
if (stack.size() < k)
if (c == letter) {
stack.push_back(c);
--required;
} else if (k > stack.size() + required) {
stack.push_back(c);
}
if (c == letter)
--nLetters;
}
for (const char c : stack)
ans += c;
return ans;
}
}; /* code provided by PROGIEZ */
2030. Smallest K-Length Subsequence With Occurrences of a Letter LeetCode Solution in Java
class Solution {
public String smallestSubsequence(String s, int k, char letter, int repetition) {
StringBuilder sb = new StringBuilder();
Deque<Character> stack = new ArrayDeque<>();
int required = repetition;
int nLetters = (int) s.chars().filter(c -> c == letter).count();
for (int i = 0; i < s.length(); ++i) {
final char c = s.charAt(i);
while (!stack.isEmpty() && stack.peek() > c && stack.size() + s.length() - i - 1 >= k &&
(stack.peek() != letter || nLetters > required))
if (stack.pop() == letter)
++required;
if (stack.size() < k)
if (c == letter) {
stack.push(c);
--required;
} else if (k - stack.size() > required) {
stack.push(c);
}
if (c == letter)
--nLetters;
}
for (final char c : stack)
sb.append(c);
return sb.reverse().toString();
}
} // code provided by PROGIEZ
2030. Smallest K-Length Subsequence With Occurrences of a Letter LeetCode Solution in Python
class Solution:
def smallestSubsequence(
self,
s: str,
k: int,
letter: str,
repetition: int,
) -> str:
stack = [] # running string
required = repetition
nLetters = s.count(letter)
for i, c in enumerate(s):
# Make sure the length is sufficient:
# Len(stack) := the length of running string
# Len(s) - i := the length of remain chars
# -1 := we're going to pop a char
while (stack and stack[-1] > c
and len(stack) + len(s) - i - 1 >= k
and (stack[-1] != letter or nLetters > required)):
if stack.pop() == letter:
required += 1
if len(stack) < k:
if c == letter:
stack.append(c)
required -= 1
elif k - len(stack) > required:
stack.append(c)
if c == letter:
nLetters -= 1
return ''.join(stack) # code by PROGIEZ
