minimum-window-substring

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given two strings <code>s</code> and <code>t</code> of lengths <code>m</code> and <code>n</code> respectively, return the minimum window substring of <code>s</code> such that every character in <code>t</code> (including duplicates) is included in the window. If there is no such substring, return the empty string <code>&quot;&quot;</code>.

The testcases will be generated such that the answer is unique.

&nbsp;
Example 1:

<pre>
Input: s = &quot;ADOBECODEBANC&quot;, t = &quot;ABC&quot;
Output: &quot;BANC&quot;
Explanation: The minimum window substring &quot;BANC&quot; includes &#39;A&#39;, &#39;B&#39;, and &#39;C&#39; from string t.
</pre>

Example 2:

<pre>
Input: s = &quot;a&quot;, t = &quot;a&quot;
Output: &quot;a&quot;
Explanation: The entire string s is the minimum window.
</pre>

Example 3:

<pre>
Input: s = &quot;a&quot;, t = &quot;aa&quot;
Output: &quot;&quot;
Explanation: Both &#39;a&#39;s from t must be included in the window.
Since the largest window of s only has one &#39;a&#39;, return empty string.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>m == s.length</code></li>
	<li><code>n == t.length</code></li>
	<li><code>1 &lt;= m, n &lt;= 105</code></li>
	<li><code>s</code> and <code>t</code> consist of uppercase and lowercase English letters.</li>
</ul>

&nbsp;
Follow up: Could you find an algorithm that runs in <code>O(m + n)</code> time?

minWindow

Minimum Window Substring

Substring with Concatenation of All Words

substring-with-concatenation-of-all-words

串联所有单词的子串

Minimum Size Subarray Sum

minimum-size-subarray-sum

长度最小的子数组

Sliding Window Maximum

sliding-window-maximum

滑动窗口最大值

Permutation in String

permutation-in-string

字符串的排列

Smallest Range Covering Elements from K Lists

smallest-range-covering-elements-from-k-lists

最小区间

Minimum Window Subsequence

minimum-window-subsequence

最小窗口子序列

Count Substrings That Can Be Rearranged to Contain a String II

count-substrings-that-can-be-rearranged-to-contain-a-string-ii

统计重新排列后包含另一个字符串的子字符串数目 II

Count Substrings That Can Be Rearranged to Contain a String I

count-substrings-that-can-be-rearranged-to-contain-a-string-i

统计重新排列后包含另一个字符串的子字符串数目 I

Hash Table

String

Sliding Window

给你一个字符串 <code>s</code> 、一个字符串 <code>t</code> 。返回 <code>s</code> 中涵盖 <code>t</code> 所有字符的最小子串。如果 <code>s</code> 中不存在涵盖 <code>t</code> 所有字符的子串，则返回空字符串 <code>""</code> 。

&nbsp;

注意：

<ul>
	<li>对于 <code>t</code> 中重复字符，我们寻找的子字符串中该字符数量必须不少于 <code>t</code> 中该字符数量。</li>
	<li>如果 <code>s</code> 中存在这样的子串，我们保证它是唯一的答案。</li>
</ul>

&nbsp;

示例 1：

<pre>
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
</pre>

示例 2：

<pre>
输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。
</pre>

示例 3:

<pre>
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。</pre>

&nbsp;

提示：

<ul>
	<li><code>m == s.length</code></li>
	<li><code>n == t.length</code></li>
	<li><code>1 &lt;= m, n &lt;= 105</code></li>
	<li><code>s</code> 和 <code>t</code> 由英文字母组成</li>
</ul>

&nbsp;
进阶：你能设计一个在 <code>o(m+n)</code> 时间内解决此问题的算法吗？