LeetCode-76. Minimum Window Substringhttps://leetcode.com/problems/minimum-window-substring/
Given two strings s
and t
of lengths m
and n
respectively, return the minimum window substring of s
such that every character in t
(including duplicates) is included in the window. If there is no such substring, return the empty string ""
.
The testcases will be generated such that the answer is unique.
A substring is a contiguous sequence of characters within the string.
Example 1:
Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC" Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.
Example 2:
Input: s = "a", t = "a" Output: "a" Explanation: The entire string s is the minimum window.
Example 3:
Input: s = "a", t = "aa" Output: "" Explanation: Both 'a's from t must be included in the window. Since the largest window of s only has one 'a', return empty string.
class Solution { public: string minWindow(string s, string t) { vector<int> ch(256, 0); for(auto c : t) ch[c]++; int b=0, e=0, cnt=t.size(), minStart=0, minL=INT_MAX; while (e<s.size()) { if(ch[s[e++]]-- > 0) cnt--; while(cnt == 0) { if(e-b < minL) {minL=e-b; minStart=b;} if(ch[s[b++]]++ == 0) cnt++; } } return minL == INT_MAX ? "" : s.substr(minStart, minL); } }
【Java】
class Solution { public String minWindow(String s, String t) { int[] ch = new int[256]; for(char c : t.toCharArray()) ch[c]++; int b=0, e=0, cnt=t.length(), minStart=0, minL=Integer.MAX_VALUE; while (e<s.length()) { if(ch[s.charAt(e++)]-- > 0) cnt--; while(cnt == 0) { if(e-b < minL) {minL=e-b; minStart=b;} if(ch[s.charAt(b++)]++ == 0) cnt++; } } return minL == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minL); } }
参考文献
【1】leetcode刷题2———子串系列_taifyang的博客-CSDN博客