727. Minimum window subsequence sliding window

727. Minimum window subsequence

Given string  S and T, find  S  The shortest one in （ continuity ） Substring  W , bring  T  yes  W  Of   Subsequence  .

If  S  No window in can contain  T  All characters in , Returns an empty string  "". If there is more than one window with the shortest length , Return to the one on the left of the starting position .

Example 1：

 Input ：
S = "abcdebdde", T = "bde"
 Output ："bcde"
 explain ：
"bcde"  Yes, the answer , Because it's in a string of the same length  "bdde"  Before appearance .
"deb"  Not a shorter answer , Because it must appear in order in the window  T  The elements in .

notes ：

• All input strings contain only lowercase letters .All the strings in the input will only contain lowercase letters.
• S  The length range is  [1, 20000].
• T  The length range is  [1, 100].

  The result of doing the question

success , Barely write it out with a sliding window

Method ： The sliding window

1. Determine starting point , Those that do not match the first character will be skipped

2. Make a perfect match , If you can complete the matching , Then add to the answer

 

class Solution {
        public String minWindow(String s1, String s2) {
            int m = s1.length();
            int n = s2.length();
            int ans = 0;
            int start = 0;
            for(int i =0 ; i < m-n+1; i++){
                while (i<m&&s1.charAt(i)!=s2.charAt(0)) ++i;
                int j = i;
                int k = 0;
                for(; j < m&&k<n; j++){
                    if (s1.charAt(j)==s2.charAt(k)){
                        ++k;
                    }
                }

                if(k==n&&(j-i<ans||ans==0)){
                    ans = j-i;
                    start = i;
                }
            }
            return s1.substring(start,start+ans);
        }
    }