Massive Algorithms: LeetCode 76

http://www.geeksforgeeks.org/find-the-smallest-window-in-a-string-containing-all-characters-of-another-string/
Given a set T of characters and a string S, find the minimum window in S which will contain all the characters in T in complexity O(n).
S = “ADOBECODEBANC”
T = “ABC”

Minimum window is “BANC”.

The idea is mainly based on the help of two pointers (begin and end position of the window) and two tables (needToFind and hasFound) while traversing S. needToFind stores the total count of a character in T and hasFound stores the total count of a character met so far. We also use a count variable to store the total characters in T that’s met so far (not counting characters where hasFound[x] exceeds needToFind[x]). When count equals T‘s length, we know a valid window is found.

https://leetcode.com/problems/minimum-window-substring/discuss/26811/Share-my-neat-java-solution
https://leetcode.com/problems/minimum-window-substring/discuss/26808/Here-is-a-10-line-template-that-can-solve-most-'substring'-problems

    public String minWindow(String s, String t) {
        int[] map = new int[128];
        int res = Integer.MAX_VALUE, left = 0, right = 0, begin = 0, counter = t.length();
        for (int i = 0; i < t.length(); i++) {
            map[t.charAt(i) - 'A']++;
        }
        while (right < s.length()) {
            if (map[s.charAt(right++) - 'A']-- > 0) counter--;  //这个数应该出现的次数减一
            while (counter == 0) {  //缩短左边界
                if (right - left < res) {
                    res = right - left;
                    begin = left;
                }
                if (map[s.charAt(left++) - 'A']++ == 0) counter++;
            }
        }
        return res == Integer.MAX_VALUE ? "" : s.substring(begin, begin + res);
    }

https://leetcode.com/articles/minimum-window-substring/
Use two pointers to create a window of letters in S, which would have all the characters from T

Since you have to find the minimum window in S which has all the characters from T, you need to expand and contract the window using the two pointers and keep checking the window for all the characters. This approach is also called Sliding Window Approach.

L ------------------------ R , Suppose this is the window that contains all characters of T 
                          
        L----------------- R , this is the contracted window. We found a smaller window that still contains all the characters in T

When the window is no longer valid, start expanding again using the right pointer

Time Complexity: $O(|S| + |T|)$ where |S| and |T| represent the lengths of strings $S$ and $T$ . In the worst case we might end up visiting every element of string $S$ twice, once by left pointer and once by right pointer. $|T|$ represents the length of string $T$ .
Space Complexity: $O(|S| + |T|)$ . $|S|$ when the window size is equal to the entire string $S$ . $|T|$ when $T$ has all unique characters.

public String minWindow(String s, String t) {

if (s.length() == 0 || t.length() == 0) {

return "";

}

// Dictionary which keeps a count of all the unique characters in t.

Map<Character, Integer> dictT = new HashMap<Character, Integer>();

for (int i = 0; i < t.length(); i++) {

int count = dictT.getOrDefault(t.charAt(i), 0);

dictT.put(t.charAt(i), count + 1);

}

// Number of unique characters in t, which need to be present in the desired window.

int required = dictT.size();

// Left and Right pointer

int l = 0, r = 0;

// formed is used to keep track of how many unique characters in t

// are present in the current window in its desired frequency.

// e.g. if t is "AABC" then the window must have two A's, one B and one C.

// Thus formed would be = 3 when all these conditions are met.

int formed = 0;

// Dictionary which keeps a count of all the unique characters in the current window.

Map<Character, Integer> windowCounts = new HashMap<Character, Integer>();

// ans list of the form (window length, left, right)

int[] ans = {-1, 0, 0};

while (r < s.length()) {

// Add one character from the right to the window

char c = s.charAt(r);

int count = windowCounts.getOrDefault(c, 0);

windowCounts.put(c, count + 1);

// If the frequency of the current character added equals to the

// desired count in t then increment the formed count by 1.

if (dictT.containsKey(c) && windowCounts.get(c).intValue() == dictT.get(c).intValue()) {

formed++;

}

// Try and contract the window till the point where it ceases to be 'desirable'.

while (l <= r && formed == required) {

c = s.charAt(l);

// Save the smallest window until now.

if (ans[0] == -1 || r - l + 1 < ans[0]) {

ans[0] = r - l + 1;

ans[1] = l;

ans[2] = r;

}

// The character at the position pointed by the

// `Left` pointer is no longer a part of the window.

windowCounts.put(c, windowCounts.get(c) - 1);

if (dictT.containsKey(c) && windowCounts.get(c).intValue() < dictT.get(c).intValue()) {

formed--;

}

// Move the left pointer ahead, this would help to look for a new window.

l++;

}

// Keep expanding the window once we are done contracting.

r++;

}

return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);

}

A small improvement to the above approach can reduce the time complexity of the algorithm to

O(2*|filtered\_S| + |S| + |T|)

, where

filtered\_S

is the string formed from S by removing all the elements not present in

T

.

This complexity reduction is evident when

|filtered\_S| &lt;&lt;&lt; |S|

.

This kind of scenario might happen when length of string

T

is way too small than the length of string

S

and string

S

consists of numerous characters which are not present in

T

.

public String minWindow(String s, String t) {

if (s.length() == 0 || t.length() == 0) {

return "";

}

Map<Character, Integer> dictT = new HashMap<Character, Integer>();

for (int i = 0; i < t.length(); i++) {

int count = dictT.getOrDefault(t.charAt(i), 0);

dictT.put(t.charAt(i), count + 1);

}

int required = dictT.size();

// Filter all the characters from s into a new list along with their index.

// The filtering criteria is that the character should be present in t.

List<Pair<Integer, Character>> filteredS = new ArrayList<Pair<Integer, Character>>();

for (int i = 0; i < s.length(); i++) {

char c = s.charAt(i);

if (dictT.containsKey(c)) {

filteredS.add(new Pair<Integer, Character>(i, c));

}

int l = 0, r = 0, formed = 0;

Map<Character, Integer> windowCounts = new HashMap<Character, Integer>();

int[] ans = { -1, 0, 0 };

// Look for the characters only in the filtered list instead of entire s.

// This helps to reduce our search.

// Hence, we follow the sliding window approach on as small list.

while (r < filteredS.size()) {

char c = filteredS.get(r).getValue();

int count = windowCounts.getOrDefault(c, 0);

windowCounts.put(c, count + 1);

if (dictT.containsKey(c) && windowCounts.get(c).intValue() == dictT.get(c).intValue()) {

formed++;

}

// Try and contract the window till the point where it ceases to be 'desirable'.

while (l <= r && formed == required) {

c = filteredS.get(l).getValue();

// Save the smallest window until now.

int end = filteredS.get(r).getKey();

int start = filteredS.get(l).getKey();

if (ans[0] == -1 || end - start + 1 < ans[0]) {

ans[0] = end - start + 1;

ans[1] = start;

ans[2] = end;

}

windowCounts.put(c, windowCounts.get(c) - 1);

if (dictT.containsKey(c) && windowCounts.get(c).intValue() < dictT.get(c).intValue()) {

formed--;

}

l++;

}

r++;

}

return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);

}

https://discuss.leetcode.com/topic/68976/sliding-window-algorithm-template-to-solve-all-the-leetcode-substring-search-problem

you may find that I only change a little code above to solve the question "Find All Anagrams in a String":
change

                if(end-begin < len){
                    len = end - begin;
                    head = begin;
                }

to

                if(end-begin == t.length()){
                    result.add(begin);
                }

    public String minWindow(String s, String t) {
        if(t.length()> s.length()) return "";
        Map<Character, Integer> map = new HashMap<>();
        for(char c : t.toCharArray()){
            map.put(c, map.getOrDefault(c,0) + 1);
        }
        int counter = map.size();
        
        int begin = 0, end = 0;
        int head = 0;
        int len = Integer.MAX_VALUE;
        
        while(end < s.length()){
            char c = s.charAt(end);
            if( map.containsKey(c) ){
                map.put(c, map.get(c)-1);
                if(map.get(c) == 0) counter--;
            }
            end++;
            
            while(counter == 0){
                char tempc = s.charAt(begin);
                if(map.containsKey(tempc)){
                    map.put(tempc, map.get(tempc) + 1);
                    if(map.get(tempc) > 0){
                        counter++;
                    }
                }
                if(end-begin < len){
                    len = end - begin;
                    head = begin;
                }
                begin++;
            }
            
        }
        if(len == Integer.MAX_VALUE) return "";
        return s.substring(head, head+len);
    }

https://discuss.leetcode.com/topic/30941/here-is-a-10-line-template-that-can-solve-most-substring-problems
https://discuss.leetcode.com/topic/12492/share-my-neat-java-solution
http://rleetcode.blogspot.com/2014/01/minimum-window-substring-java.html

http://www.cnblogs.com/lichen782/p/leetcode_minimum_window_substring_3.html
https://discuss.leetcode.com/topic/21143/java-solution-using-two-pointers-hashmap
http://www.jiuzhang.com/solutions/minimum-window-substring/

public String minWindow3(String S, String T){
 2         HashMap<Character, Integer> needToFill = new HashMap<Character, Integer>();
 3         HashMap<Character, Integer> hasFound = new HashMap<Character, Integer>();
 4         int count = 0;
 5         for(int i = 0; i < T.length(); i++){
 6             if(!needToFill.containsKey(T.charAt(i))){
 7                 needToFill.put(T.charAt(i), 1);
 8                 hasFound.put(T.charAt(i), 0);
 9             }else {
10                 needToFill.put(T.charAt(i), needToFill.get(T.charAt(i)) + 1);
11             }
12         }
13         int minWinBegin = -1;
14         int minWinEnd = S.length();
15         for(int begin = 0, end = 0; end < S.length(); end++){
16             char c = S.charAt(end);
17             if(needToFill.containsKey(c)){
18                 hasFound.put(c, hasFound.get(c) + 1);
19                 if(hasFound.get(c) <= needToFill.get(c)){
20                     count++;
21                 }
22                 if(count == T.length()){
23                     while(!needToFill.containsKey(S.charAt(begin)) ||
24                             hasFound.get(S.charAt(begin)) > needToFill.get(S.charAt(begin))) {
25                         if(needToFill.containsKey(S.charAt(begin)) 
26                                 && hasFound.get(S.charAt(begin)) > needToFill.get(S.charAt(begin))){
27                             hasFound.put(S.charAt(begin), hasFound.get(S.charAt(begin)) - 1);
28                         }
29                         begin++;
30                     }
31                     if(end - begin < minWinEnd - minWinBegin){
32                         minWinEnd = end;
33                         minWinBegin = begin;
34                     }
35                 }
36             }
37         }
38         return minWinBegin == -1 ? "" : S.substring(minWinBegin, minWinEnd + 1);

http://n00tc0d3r.blogspot.com/2013/04/minimum-window-substring.html

No need to use nexts list.

  * Two pointers: one for window_left and one for window_right  
  * As moving to the right, we know which char is in T,  
  * store the index into an array so that left point can directly  
  * jump to next spot.  
  */  
 public String minWindow(String S, String T) {  
   int ss = S.length(), tt = T.length();  
   // build up hashmap for T and also keep track of occurrence  
   HashMap<Character, Integer> needFind = new HashMap<Character, Integer>();  
   HashMap<Character, Integer> hasFound = new HashMap<Character, Integer>();  
   for (int i=0; i<tt; ++i) {  
     hasFound.put(T.charAt(i), 0);  
     if (needFind.containsKey(T.charAt(i))) {  
       needFind.put(T.charAt(i), needFind.get(T.charAt(i))+1);  
     } else {  
       needFind.put(T.charAt(i), 1);  
     }  
   }  

   // keep found T-letters in an array to avoid revisit non-T-letters when forwarding left
   ArrayList<Integer> nexts = new ArrayList<Integer>();  
   // window = S[nexts.get(left), S[right]]
   int right = 0, found = 0, left = 0;  

   // sliding window as needed  
   String window = "";  
   int winSize = Integer.MAX_VALUE;  
   while (right < S.length()) {  
     char c = S.charAt(right);  
     if (!needFind.containsKey(c)) { // not a match  
       ++right;  
       continue;  
     }  
   
     nexts.add(right);  
     ++right;  
     hasFound.put(c, hasFound.get(c)+1);  
     if (hasFound.get(c) <= needFind.get(c)) ++found;  
   
     if (found >= tt) { // got a window  
       // forward left?  
       char ll = S.charAt(nexts.get(left));  
       while (hasFound.get(ll) > needFind.get(ll)) {  
         hasFound.put(ll, hasFound.get(ll)-1);  
         ++left;  
         ll = S.charAt(nexts.get(left));  
       }  
       // smaller window?  
       if (right - nexts.get(left) < winSize) {  
         winSize = right - nexts.get(left);  
         window = S.substring(nexts.get(left), right);  
       }  
     }  
   }  
   return window;  
 }

X. Use count array
https://leetcode.com/discuss/90376/o-n-5ms-java-solution-beats-93-18%25
public String minWindow(String s, String t) { char[] needToFind = new char[256]; char[] hasFound = new char[256]; int sLen = s.length(); int tLen = t.length(); int count = 0; int optLen = Integer.MAX_VALUE; // opt stands for optimal int optBegin = 0; int optEnd = 0; for (int i = 0; i < tLen; i++) { // gives a counter for each character in t needToFind[t.charAt(i)]++; } for (int begin = 0, end = 0; end < sLen; end++) { if (needToFind[s.charAt(end)] == 0) { // skips irrelevant char continue; } char currEnd = s.charAt(end); // the char at the end hasFound[currEnd]++; if (hasFound[currEnd] <= needToFind[currEnd]) { count++; } if (count == tLen) { // pauses end, moves beginning to the right as much as possible char currBegin = s.charAt(begin); // char at begin while (hasFound[currBegin] > needToFind[currBegin] || needToFind[currBegin] == 0) { if (hasFound[currBegin] > needToFind[currBegin]) { hasFound[currBegin]--; } begin++; currBegin = s.charAt(begin); } if (optLen > end - begin + 1) { // if current length is smaller, update our optimum solution optLen = end - begin + 1; optBegin = begin; optEnd = end; } } } if (count != tLen) { return ""; } return s.substring(optBegin, optEnd + 1); }
https://leetcode.com/discuss/32851/share-my-neat-java-solution

public String minWindow(String S, String T) { if(S==null||S.isEmpty()||T==null||T.isEmpty()) return ""; int i=0, j=0; int[] Tmap=new int[256]; int[] Smap=new int[256]; for(int k=0; k< T.length(); k++){ Tmap[T.charAt(k)]++; } int found=0; int length=Integer.MAX_VALUE; String res=""; while(j<S.length()){ if(found<T.length()){ if(Tmap[S.charAt(j)]>0){ Smap[S.charAt(j)]++; if(Smap[S.charAt(j)]<=Tmap[S.charAt(j)]){ found++; } } j++; } while(found==T.length()){ if(j-i<length){ length=j-i; res=S.substring(i,j); } if(Tmap[S.charAt(i)]>0){ Smap[S.charAt(i)]--; if(Smap[S.charAt(i)]<Tmap[S.charAt(i)]){ found--; } } i++; } } return res; }
Time Complexity: O(n)

bool minWindow(const char* S, const char *T, 

               int &minWindowBegin, int &minWindowEnd) {

  int sLen = strlen(S);

  int tLen = strlen(T);

  int needToFind[256] = {0};

  for (int i = 0; i < tLen; i++)

    needToFind[T[i]]++;

  int hasFound[256] = {0};

  int minWindowLen = INT_MAX;

  int count = 0;

  for (int begin = 0, end = 0; end < sLen; end++) {

    // skip characters not in T

    if (needToFind[S[end]] == 0) continue;

    hasFound[S[end]]++;

    if (hasFound[S[end]] <= needToFind[S[end]])

      count++;

    // if window constraint is satisfied

    if (count == tLen) {

      // advance begin index as far right as possible,

      // stop when advancing breaks window constraint.

      while (needToFind[S[begin]] == 0 ||

            hasFound[S[begin]] > needToFind[S[begin]]) {

        if (hasFound[S[begin]] > needToFind[S[begin]])

          hasFound[S[begin]]--;

        begin++;

}

      // update minWindow if a minimum length is met

      int windowLen = end - begin + 1;

      if (windowLen < minWindowLen) {

        minWindowBegin = begin;

        minWindowEnd = end;

        minWindowLen = windowLen;

      } // end if

    } // end if

  } // end for

  return (count == tLen) ? true : false;

}

X. Not good:
https://leetcode.com/discuss/23760/accepted-solution-for-your-reference
https://leetcode.com/discuss/62495/o-n-java-sliding-window-solution-with-explanation
boolean sContainsT(int mapS[], int mapT[]) {// Runtime = O(256) = O(1) for (int i = 0; i < mapT.length; i++) {// s should cover all characters in t if (mapT[i] > mapS[i]) return false; } return true; } public String minWindow(String s, String t) { int mapS[] = new int[256];// Count characters in s int mapT[] = new int[256];// Count characters in t for (char ch : t.toCharArray()) mapT[ch]++; String res = ""; int right = 0, min = Integer.MAX_VALUE; for (int i = 0; i < s.length(); i++) {// Two pointers of the sliding window: i(left), right while (right < s.length() && !sContainsT(mapS, mapT)) {// Extend the right pointer of the sliding window mapS[s.charAt(right)]++; right++; } if (sContainsT(mapS, mapT) && min > right - i + 1) { res = s.substring(i, right); min = right - i + 1; } mapS[s.charAt(i)]--;// Shrink the left pointer from i to i + 1 } return res; }
Related: http://blueocean-penn.blogspot.com/2015/11/minimum-consecutive-sub-string-of-s.html
Given a random string S and another string T with unique elements. find the minimum consecutive sub-string of S such that it contains all the elements in T/
==> No duplicated in T.example:
S='adobecodebanc'
T='abc'
answer='banc"

We need a sliding window algorithm to solve this problem. The window data structure needs to tell us few things: 1) are all characters in T found in the window? 2) how many times of each character found in the window appears so far? 3) if all characters are found in the window, can we shrink the window?

To answer question 1 and 2, we can maintain a hashMap, its key is the character found, the value is the numbers of times the character appears in the window.
To answer question 3, we need to maintain a data structure which can 1) represent the sliding window; 2) shrink the window if the number of first character in the window is more than once. We will use a Queue to do that, a double-ended queue actually in the below implementation.
public static String miniSubstr(String s, String t){
        Deque<Item> q = new ArrayDeque<Item>();
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        int p=0, min=Integer.MAX_VALUE;
        String result = null;
        while(p<s.length()){
            char c = s.charAt(p);
            if(t.indexOf(c)>-1){ // it's better to first build a hashmap of t.
                //update the sliding window
                q.add(new Item(c, p));
                //update the counter map
                if(!map.containsKey(c))
                    map.put(c, 1);
                else
                    map.put(c, map.get(c)+1);
                //shrink the sliding window if char in the head of q appears more than once
                while(true){
                    Item item = q.peek();
                    Integer num = map.get(item.c);
                    if(num>1){
                        q.removeFirst();
                        map.put(item.c, num-1);
                    }else
                        break;
                }
            }

            //when we find all characters, then we update result
            if(map.size() == t.length()){
                int current = q.peekLast().p - q.peekFirst().p;
                if(current<min){
                    min = current;
                    result = s.substring(q.peekFirst().p, q.peekLast().p+1);
                }
            }

            p++;
        }
        return result;
    }

    static class Item{
        char c; // value
        int p; // index
        Item(char c, int t){
            this.c = c; this.p = t;
        }
    }

TODO: http://allenlipeng47.com/PersonalPage/index/view/198/nkey
The idea is to maintain a double-linked-list.
Also check http://www.geeksforgeeks.org/find-the-smallest-window-in-a-string-containing-all-characters-of-another-string/
http://yihuad.blogspot.com/2013/10/minimum-window-substring-leetcode.html

http://www.1point3acres.com/bbs/thread-199194-1-1.html

给定一个句子, 和若干个搜索词, 求包含所有搜索词的最短句子长度.
Badmin was able to beat Bill at billiards, but Bill always beat Badmin badly at badminton.

给定搜索词: Query = [Badmin, Bill, beat]
返回 4. 因为子句(Bill always beat Badmin)是包含Query中所有单词的最短子句.

提示: 可以将子句看成倒排的形式如:

"Badmin" = [0, 12]
"Bill" = [5, 9]
"beat" = [4, 11]
其中倒排中的每个index是递增的, 可以利用这点剪枝(?)
这是我面试遇到的问题, 我只想到了暴力解, 就是用dfs枚举所有. 希望大家提供更好的解

http://www.1point3acres.com/bbs/thread-166355-1-1.html
求string str1中含有string str2 order的 subsequence 的最小长度
举个例子： str1 = "acbacbc" str2="abc", 那么最小subsequence长度应该是4，对应的subsequence是“acbc”

类似于 LC 76. Minimum Window Substring。但需要保持order

那道题要用array或者hashmap记录char出现次数，找到一个合适窗口后，尝试移动左边缘缩小窗口。这道题找到一个合适窗口倒不难，但是该怎么optimize窗口大小呢

对，我写的比较naive的dp，时间复杂度应该可以优化到O(n^2)，去掉第三个循环，可以在第二个循环遍历的时候同时记录见到上一次字符最小长度。类似buy and sell stock IV的优化方法。

你的暴力解法是怎么做？如果拆下来n^2个substring的话，和另外一个string的比较还需要O(n)的时间。我这个dp是最简单的版本，应该可以优化到O(m*n)
暴力就是O(n^2):
遍历str1,如果某个char i和str2的第一个char相同，就从i开始往后遍历所有字符，直到找到str2对应的sequence，或者走完str1,由于这里是同时递增遍历str1,str2，所以时间复杂度是O(n); 然后接着从i + 1开始遍历str1.总的复杂度是O(n^2). 实际跟strStr类似，那个的复杂度是O(mn),现在条件更复杂，谨慎怀疑一般的做法是否能到O(mn)。
嗯，这样看来没必要dp做。

求问这个双指针怎么做？尤其是可能pattern还会有重复的char，这样感觉最少也要O( lenA * lenB )

kmp?

用三个指针就行了，时间复杂度O(n^2)，空间复杂度O(1)

public static void main(String[] args) {
System.out.println(getShortestSequence("acbacbc", "abc"));. visit 1point3acres.com for more.
}
public static int getShortestSequence(String s1, String s2) {
if (s1.length() < s2.length()) {.1point3acres缃�
return Integer.MAX_VALUE;-google 1point3acres
}
int res = Integer.MAX_VALUE;
for (int i = 0; i < s1.length(); i++) {
if (s1.charAt(i) == s2.charAt(0)) {
int j = i;
int k = 0;
while (j < s1.length() && k < s2.length()) {
if (s1.charAt(j) == s2.charAt(k)) {
j++;
k++;
} else {
j++;. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
}
}
if (k == s2.length()) {
res = Math.min(res, j - i);
}
}
}. 1point 3acres 璁哄潧
return res;. Waral 鍗氬鏈夋洿澶氭枃绔�,
}

dp:
pattern对应到i位置，string对应到j位置时，shortest substring的长度，Int_Max表示不存在

public String findShortest(String a, String b){
if(a==null || b==null || a.length()==0 || b.length()==0) throw new IllegalArgumentException();
. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
int lena = a.length(), lenb = b.length();.鏈枃鍘熷垱鑷�1point3acres璁哄潧
int[][] dp = new int[lenb][lena];
for(int i=0; i<lenb; i++){
char bc = b.charAt(i);
for(int j=0; j<lena; j++){
char ac = a.charAt(j);.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
dp[i][j] = Integer.MAX_VALUE;
if(ac==bc){
if(i==0) dp[i][j] = 1;
else {
for (int t = 0; t < j; t++) {
if (dp[i - 1][t] == Integer.MAX_VALUE) continue;
else dp[i][j] = Math.min(dp[i][j], dp[i - 1][t] + j - t);
}. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
}
}
}
}
int min = Integer.MAX_VALUE;
int end = -1;-google 1point3acres
for(int j=0; j<lena; j++){
if(dp[lenb-1][j] < min) {
min = dp[lenb-1][j];. 1point 3acres 璁哄潧
end = j;-google 1point3acres
}. 鍥磋鎴戜滑@1point 3 acres
}
// System.out.println(end);
// System.out.println(min);
.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
if(end==-1) return "no match!";.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
return a.substring(end-min+1, end+1);
}

https://github.com/mintycc/OnlineJudge-Solutions/blob/master/Leetcode/076_Minimum_Window_Substring.java
如果允许⼀一个字⺟母不不⼀一样 str1 = acedbg, str2 = xcbe，那么返回cedb

LeetCode 76 - Minimum Window Substring

Labels

Popular Posts