shortest-and-lexicographically-smallest-beautiful-string

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 binary string <code>s</code> and a positive integer <code>k</code>.

A substring of <code>s</code> is beautiful if the number of <code>1</code>&#39;s in it is exactly <code>k</code>.

Let <code>len</code> be the length of the shortest beautiful substring.

Return the lexicographically smallest beautiful substring of string <code>s</code> with length equal to <code>len</code>. If <code>s</code> doesn&#39;t contain a beautiful substring, return an empty string.

A string <code>a</code> is lexicographically larger than a string <code>b</code> (of the same length) if in the first position where <code>a</code> and <code>b</code> differ, <code>a</code> has a character strictly larger than the corresponding character in <code>b</code>.

<ul>
	<li>For example, <code>&quot;abcd&quot;</code> is lexicographically larger than <code>&quot;abcc&quot;</code> because the first position they differ is at the fourth character, and <code>d</code> is greater than <code>c</code>.</li>
</ul>

&nbsp;
Example 1:

<pre>
Input: s = &quot;100011001&quot;, k = 3
Output: &quot;11001&quot;
Explanation: There are 7 beautiful substrings in this example:
1. The substring &quot;100011001&quot;.
2. The substring &quot;100011001&quot;.
3. The substring &quot;100011001&quot;.
4. The substring &quot;100011001&quot;.
5. The substring &quot;100011001&quot;.
6. The substring &quot;100011001&quot;.
7. The substring &quot;100011001&quot;.
The length of the shortest beautiful substring is 5.
The lexicographically smallest beautiful substring with length 5 is the substring &quot;11001&quot;.
</pre>

Example 2:

<pre>
Input: s = &quot;1011&quot;, k = 2
Output: &quot;11&quot;
Explanation: There are 3 beautiful substrings in this example:
1. The substring &quot;1011&quot;.
2. The substring &quot;1011&quot;.
3. The substring &quot;1011&quot;.
The length of the shortest beautiful substring is 2.
The lexicographically smallest beautiful substring with length 2 is the substring &quot;11&quot;.
</pre>

Example 3:

<pre>
Input: s = &quot;000&quot;, k = 1
Output: &quot;&quot;
Explanation: There are no beautiful substrings in this example.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= s.length &lt;= 100</code></li>
	<li><code>1 &lt;= k &lt;= s.length</code></li>
</ul>

shortestBeautifulSubstring

Shortest and Lexicographically Smallest Beautiful String

String

Sliding Window

给你一个二进制字符串 <code>s</code> 和一个正整数 <code>k</code> 。

如果 <code>s</code> 的某个子字符串中 <code>1</code> 的个数恰好等于 <code>k</code> ，则称这个子字符串是一个 美丽子字符串 。

令 <code>len</code> 等于 最短 美丽子字符串的长度。

返回长度等于 <code>len</code> 且字典序 最小 的美丽子字符串。如果 <code>s</code> 中不含美丽子字符串，则返回一个 空 字符串。

对于相同长度的两个字符串 <code>a</code> 和 <code>b</code> ，如果在 <code>a</code> 和 <code>b</code> 出现不同的第一个位置上，<code>a</code> 中该位置上的字符严格大于 <code>b</code> 中的对应字符，则认为字符串 <code>a</code> 字典序 大于 字符串 <code>b</code> 。

<ul>
	<li>例如，<code>"abcd"</code> 的字典序大于 <code>"abcc"</code> ，因为两个字符串出现不同的第一个位置对应第四个字符，而 <code>d</code> 大于 <code>c</code> 。</li>
</ul>

&nbsp;

示例 1：

<pre>
输入：s = "100011001", k = 3
输出："11001"
解释：示例中共有 7 个美丽子字符串：
1. 子字符串 "100011001" 。
2. 子字符串 "100011001" 。
3. 子字符串 "100011001" 。
4. 子字符串 "100011001" 。
5. 子字符串 "100011001" 。
6. 子字符串 "100011001" 。
7. 子字符串 "100011001" 。
最短美丽子字符串的长度是 5 。
长度为 5 且字典序最小的美丽子字符串是子字符串 "11001" 。
</pre>

示例 2：

<pre>
输入：s = "1011", k = 2
输出："11"
解释：示例中共有 3 个美丽子字符串：
1. 子字符串 "1011" 。
2. 子字符串 "1011" 。
3. 子字符串 "1011" 。
最短美丽子字符串的长度是 2 。
长度为 2 且字典序最小的美丽子字符串是子字符串 "11" 。 
</pre>

示例 3：

<pre>
输入：s = "000", k = 1
输出：""
解释：示例中不存在美丽子字符串。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= s.length &lt;= 100</code></li>
	<li><code>1 &lt;= k &lt;= s.length</code></li>
</ul>