minimum-window-substring

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

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

给定两个字符串&nbsp;<code>s</code> 和&nbsp;<code>t</code>，长度分别是&nbsp;<code>m</code> 和&nbsp;<code>n</code>，返回 s 中的&nbsp;最短窗口 子串，使得该子串包含 <code>t</code> 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串&nbsp;<code>""</code>。

测试用例保证答案唯一。

&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> 时间内解决此问题的算法吗？