smallest-k-length-subsequence-with-occurrences-of-a-letter

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a string <code>s</code>, an integer <code>k</code>, a letter <code>letter</code>, and an integer <code>repetition</code>.

Return the lexicographically smallest subsequence of <code>s</code> of length <code>k</code> that has the letter <code>letter</code> appear at least <code>repetition</code> times. The test cases are generated so that the <code>letter</code> appears in <code>s</code> at least <code>repetition</code> 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 <code>a</code> is lexicographically smaller than a string <code>b</code> if in the first position where <code>a</code> and <code>b</code> differ, string <code>a</code> has a letter that appears earlier in the alphabet than the corresponding letter in <code>b</code>.

&nbsp;
Example 1:

<pre>
Input: s = &quot;leet&quot;, k = 3, letter = &quot;e&quot;, repetition = 1
Output: &quot;eet&quot;
Explanation: There are four subsequences of length 3 that have the letter &#39;e&#39; appear at least 1 time:
- &quot;lee&quot; (from &quot;leet&quot;)
- &quot;let&quot; (from &quot;leet&quot;)
- &quot;let&quot; (from &quot;leet&quot;)
- &quot;eet&quot; (from &quot;leet&quot;)
The lexicographically smallest subsequence among them is &quot;eet&quot;.
</pre>

Example 2:
<img alt="example-2" src="https://assets.leetcode.com/uploads/2021/09/13/smallest-k-length-subsequence.png" style="width: 339px; height: 67px;" />
<pre>
Input: s = &quot;leetcode&quot;, k = 4, letter = &quot;e&quot;, repetition = 2
Output: &quot;ecde&quot;
Explanation: &quot;ecde&quot; is the lexicographically smallest subsequence of length 4 that has the letter &quot;e&quot; appear at least 2 times.
</pre>

Example 3:

<pre>
Input: s = &quot;bb&quot;, k = 2, letter = &quot;b&quot;, repetition = 2
Output: &quot;bb&quot;
Explanation: &quot;bb&quot; is the only subsequence of length 2 that has the letter &quot;b&quot; appear at least 2 times.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= repetition &lt;= k &lt;= s.length &lt;= 5 * 104</code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
	<li><code>letter</code> is a lowercase English letter, and appears in <code>s</code> at least <code>repetition</code> times.</li>
</ul>

smallestSubsequence

Smallest K-Length Subsequence With Occurrences of a Letter

Remove Duplicate Letters

remove-duplicate-letters

去除重复字母

Subarray With Elements Greater Than Varying Threshold

subarray-with-elements-greater-than-varying-threshold

元素值大于变化阈值的子数组

Find the Lexicographically Smallest Valid Sequence

find-the-lexicographically-smallest-valid-sequence

字典序最小的合法序列

Stack

Greedy

String

Monotonic Stack

给你一个字符串 <code>s</code> ，一个整数 <code>k</code> ，一个字母 <code>letter</code> 以及另一个整数 <code>repetition</code> 。

返回 <code>s</code> 中长度为 <code>k</code> 且 字典序最小 的子序列，该子序列同时应满足字母 <code>letter</code> 出现 至少 <code>repetition</code> 次。生成的测试用例满足 <code>letter</code> 在 <code>s</code> 中出现 至少 <code>repetition</code> 次。

子序列 是由原字符串删除一些（或不删除）字符且不改变剩余字符顺序得到的剩余字符串。

字符串 <code>a</code> 字典序比字符串 <code>b</code> 小的定义为：在 <code>a</code> 和 <code>b</code> 出现不同字符的第一个位置上，字符串 <code>a</code> 的字符在字母表中的顺序早于字符串 <code>b</code>&nbsp;的字符。

&nbsp;

示例 1：

<pre>
输入：s = "leet", k = 3, letter = "e", repetition = 1
输出："eet"
解释：存在 4 个长度为 3 ，且满足字母 'e' 出现至少 1 次的子序列：
- "lee"（"leet"）
- "let"（"leet"）
- "let"（"leet"）
- "eet"（"leet"）
其中字典序最小的子序列是 "eet" 。
</pre>

示例 2：

<img alt="example-2" src="https://assets.leetcode.com/uploads/2021/09/13/smallest-k-length-subsequence.png" style="width: 339px; height: 67px;" />

<pre>
输入：s = "leetcode", k = 4, letter = "e", repetition = 2
输出："ecde"
解释："ecde" 是长度为 4 且满足字母 "e" 出现至少 2 次的字典序最小的子序列。
</pre>

示例 3：

<pre>
输入：s = "bb", k = 2, letter = "b", repetition = 2
输出："bb"
解释："bb" 是唯一一个长度为 2 且满足字母 "b" 出现至少 2 次的子序列。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= repetition &lt;= k &lt;= s.length &lt;= 5 * 104</code></li>
	<li><code>s</code> 由小写英文字母组成</li>
	<li><code>letter</code> 是一个小写英文字母，在 <code>s</code>&nbsp;中至少出现 <code>repetition</code> 次</li>
</ul>