Sliding Window algorithm template to solve all the Leetcode substring search problem.


  • 152

    Among all leetcode questions, I find that there are at least 5 substring search problem which could be solved by the sliding window algorithm.
    so I sum up the algorithm template here. wish it will help you!

    1. the template:
    public class Solution {
        public List<Integer> slidingWindowTemplateByHarryChaoyangHe(String s, String t) {
            //init a collection or int value to save the result according the question.
            List<Integer> result = new LinkedList<>();
            if(t.length()> s.length()) return result;
            
            //create a hashmap to save the Characters of the target substring.
            //(K, V) = (Character, Frequence of the Characters)
            Map<Character, Integer> map = new HashMap<>();
            for(char c : t.toCharArray()){
                map.put(c, map.getOrDefault(c, 0) + 1);
            }
            //maintain a counter to check whether match the target string.
            int counter = map.size();//must be the map size, NOT the string size because the char may be duplicate.
            
            //Two Pointers: begin - left pointer of the window; end - right pointer of the window
            int begin = 0, end = 0;
            
            //the length of the substring which match the target string.
            int len = Integer.MAX_VALUE; 
            
            //loop at the begining of the source string
            while(end < s.length()){
                
                char c = s.charAt(end);//get a character
                
                if( map.containsKey(c) ){
                    map.put(c, map.get(c)-1);// plus or minus one
                    if(map.get(c) == 0) counter--;//modify the counter according the requirement(different condition).
                }
                end++;
                
                //increase begin pointer to make it invalid/valid again
                while(counter == 0 /* counter condition. different question may have different condition */){
                    
                    char tempc = s.charAt(begin);//***be careful here: choose the char at begin pointer, NOT the end pointer
                    if(map.containsKey(tempc)){
                        map.put(tempc, map.get(tempc) + 1);//plus or minus one
                        if(map.get(tempc) > 0) counter++;//modify the counter according the requirement(different condition).
                    }
                    
                    /* save / update(min/max) the result if find a target*/
                    // result collections or result int value
                    
                    begin++;
                }
            }
            return result;
        }
    }
    
    1. Firstly, here is my sliding solution this question. I will sum up the template below this code.

    2) the similar questions are:

    https://leetcode.com/problems/minimum-window-substring/
    https://leetcode.com/problems/longest-substring-without-repeating-characters/
    https://leetcode.com/problems/substring-with-concatenation-of-all-words/
    https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/
    https://leetcode.com/problems/find-all-anagrams-in-a-string/

    3) I will give my solution for these questions use the above template one by one

    Minimum-window-substring
    https://leetcode.com/problems/minimum-window-substring/

    public class Solution {
        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);
        }
    }
    

    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);
                    }
    

    longest substring without repeating characters
    https://leetcode.com/problems/longest-substring-without-repeating-characters/

    public class Solution {
        public int lengthOfLongestSubstring(String s) {
            Map<Character, Integer> map = new HashMap<>();
            int begin = 0, end = 0, counter = 0, d = 0;
    
            while (end < s.length()) {
                // > 0 means repeating character
                //if(map[s.charAt(end++)]-- > 0) counter++;
                char c = s.charAt(end);
                map.put(c, map.getOrDefault(c, 0) + 1);
                if(map.get(c) > 1) counter++;
                end++;
                
                while (counter > 0) {
                    //if (map[s.charAt(begin++)]-- > 1) counter--;
                    char charTemp = s.charAt(begin);
                    if (map.get(charTemp) > 1) counter--;
                    map.put(charTemp, map.get(charTemp)-1);
                    begin++;
                }
                d = Math.max(d, end - begin);
            }
            return d;
        }
    }
    

    Longest Substring with At Most Two Distinct Characters
    https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/

    public class Solution {
        public int lengthOfLongestSubstringTwoDistinct(String s) {
            Map<Character,Integer> map = new HashMap<>();
            int start = 0, end = 0, counter = 0, len = 0;
            while(end < s.length()){
                char c = s.charAt(end);
                map.put(c, map.getOrDefault(c, 0) + 1);
                if(map.get(c) == 1) counter++;//new char
                end++;
                while(counter > 2){
                    char cTemp = s.charAt(start);
                    map.put(cTemp, map.get(cTemp) - 1);
                    if(map.get(cTemp) == 0){
                        counter--;
                    }
                    start++;
                }
                len = Math.max(len, end-start);
            }
            return len;
        }
    }
    

    Substring with Concatenation of All Words
    https://leetcode.com/problems/substring-with-concatenation-of-all-words/

    public class Solution {
        public List<Integer> findSubstring(String S, String[] L) {
            List<Integer> res = new LinkedList<>();
            if (L.length == 0 || S.length() < L.length * L[0].length())   return res;
            int N = S.length();
            int M = L.length; // *** length
            int wl = L[0].length();
            Map<String, Integer> map = new HashMap<>(), curMap = new HashMap<>();
            for (String s : L) {
                if (map.containsKey(s))   map.put(s, map.get(s) + 1);
                else                      map.put(s, 1);
            }
            String str = null, tmp = null;
            for (int i = 0; i < wl; i++) {
                int count = 0;  // remark: reset count 
                int start = i;
                for (int r = i; r + wl <= N; r += wl) {
                    str = S.substring(r, r + wl);
                    if (map.containsKey(str)) {
                        if (curMap.containsKey(str))   curMap.put(str, curMap.get(str) + 1);
                        else                           curMap.put(str, 1);
                        
                        if (curMap.get(str) <= map.get(str))    count++;
                        while (curMap.get(str) > map.get(str)) {
                            tmp = S.substring(start, start + wl);
                            curMap.put(tmp, curMap.get(tmp) - 1);
                            start += wl;
                            
                            //the same as https://leetcode.com/problems/longest-substring-without-repeating-characters/
                            if (curMap.get(tmp) < map.get(tmp)) count--;
                            
                        }
                        if (count == M) {
                            res.add(start);
                            tmp = S.substring(start, start + wl);
                            curMap.put(tmp, curMap.get(tmp) - 1);
                            start += wl;
                            count--;
                        }
                    }else {
                        curMap.clear();
                        count = 0;
                        start = r + wl;//not contain, so move the start
                    }
                }
                curMap.clear();
            }
            return res;
        }
    }
    

    Find All Anagrams in a String
    https://leetcode.com/problems/find-all-anagrams-in-a-string/

    public class Solution {
        public List<Integer> findAnagrams(String s, String t) {
            List<Integer> result = new LinkedList<>();
            if(t.length()> s.length()) return result;
            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 == t.length()){
                        result.add(begin);
                    }
                    begin++;
                }
                
            }
            return result;
        }
    }
    

  • 0
    J

    @HarryChaoyangHe Excellent. I loved the way you analyzed.


  • 0
    A

    Nice template, thanks! It seems we can add "longest substring with at most k distinct characters" to this list as well.


  • 0
    B

    Great template, I love it! Thank you for sharing.


  • 7

    @HarryChaoyangHe Outstanding work! FWIW, there are some more problems to which your template can be applied.

    Longest Substring with At Most K Distinct Characters
    https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters

        public int lengthOfLongestSubstringKDistinct(String s, int k) {
            if (s == null || s.isEmpty()) return 0;
            int maxLen = 0, left = 0, right = 0, counter = 0;
            Map<Character, Integer> map = new HashMap<>();
            while(right < s.length()) {
            	char ch = s.charAt(right++);
            	map.put(ch, map.getOrDefault(ch, 0) + 1);
            	if (map.size() > k) counter++;
            	while(counter > 0) {
            		char tmp = s.charAt(left);
            		map.put(tmp, map.get(tmp) - 1);
            		if (map.get(tmp) == 0) {
            			map.remove(tmp);
            			counter--;
            		}
            		left++;
            	}
            	maxLen = Math.max(maxLen, right - left);
            	
            }
            return maxLen;        
        }
    

    Longest Repeating Character Replacement
    https://leetcode.com/problems/longest-repeating-character-replacement

        public int characterReplacement(String s, int k) {
        	if (s == null || s.isEmpty()) return 0;
        	int left = 0, right = 0, counter = 0, res = 0;
        	Map<Character, Integer> map = new HashMap<>();
        	while(right < s.length()) {
        		char ch = s.charAt(right++);
        		map.put(ch, map.getOrDefault(ch, 0) + 1);
        		if (counter < map.get(ch)) counter = map.get(ch);
        		// check how many chars to "flip" by looking at the delta between the
        		// length of the string and the highest frequency char. If <= k, no problem. Otherwise, move window
        		while(!(right - left - counter <= k)) { // apply De Morgan and make it right - left - counter > k
        			char tmp = s.charAt(left);
        			map.put(tmp, map.get(tmp) - 1);
        			counter = getMax(map);
        			left++;
        		}
        		res = Math.max(res, right - left);
        	}    	
        	return res;
        }
        
        private int getMax(Map<Character, Integer> map) {
    		int max = 0;
    		for(int freq : map.values()) {
    			max = Math.max(max, freq);
    		}
    		return max;
        }
    

  • 0
    Z

    what a great solutions


  • 0
    I

    Hi there! Thanks for the awesome summary.
    Could you answer a few questions of mine?

    When iterating end, when it makes counter == 0, what does this mean right now?
    When counter == 0, and we are iterating begin, and sometimes it makes map.get(tempc) > 0, and now we imcrement counter, why is this?
    Finally, as long as counter == 0, every iteration we ask if end - begin == t.length, is this necessary?

    Thank you!


  • 16
    C

    @ian34
    In "438. Find All Anagrams in a String" problem, the counter means the number of keys contained in hash table for string p. Because we want to find all t's anagrams in s, we want to check all substring that matches t's anagrams.
    How can we check it? We can use a end pointer to go through s to check if an element in s matches an element in t.

    For example, if t = 'abb', s = 'abbabb'.
    Here we can create a hash table for string t :
    Key (Value) : a(1), b(2). [Here, counter =2]
    When iterating end, when it makes counter == 0, it means : substring 'abb' of s is an anagram of p. (This is because, we only decrement counter when the value of end is 0.
    Now, the hash table is : Key (Value) : a(0), b(0). [Here, counter =0, we increment end.]

    Knowing this, we want to continue checking whether "bba"is an anagram of t. Here, we update the begin pointer to the second char of s. Before we do so, we have to check if there is some impact by pervious begin, which is the first char of s. Because we slid the window to s.substring(1,4) instead of s.substring(0,3), we want to get rid of the previous impact of first char of s.

    We use map.get(tempc) > 0 to check whether or not s.charAt(begin) is matched with a key in hash table before . If it is matched before, we should increase counter because it would be unmatched when we only want to check s.substring(0,3).

    Why use map.get(tempc) > 0 ? Because in the outer while loop, for each char that is matched, its value must be larger than 0. (Because the char have to be in hash table.) In the outer while loop, we decrement the its value by 1, in the inner while loop, we increment its value by it. So, after all, its value should be larger than 0.

    Finally, we should check end - begin == t.length, because we want to make sure our matched substring have the same length with string t. The counter doesn't check the length for us, it only check whether all chars in string t can be found in s.substring.

    It takes me a while to understand the solution.
    I hope it helps : )


  • 1
    F

    To whom may not get the idea of this method:

    You can try to name the hashmap as StillNeed (Meaning if you want to establish an anagram of string p, you still need how many characters), then you will get the idea, it's brilliant.


  • 0
    E

    @HarryChaoyangHe hey, can u explain the loop to increase left pointer? Can't get why check counter is 0


  • 0
    E

    @chenliuliu can u elaborate more on the inner loop logic? i can't get the point of checking only the counter == 0. once the counter is back to 0+, the loop stops? also, why keep checking the end-begin?


  • 0
    S

    Complexity of this O(n) assuming dictionary access is O(1) - thanks for sharing.

    Succintly put

    • window opens as right edge expands, characters in pattern are injected in window
    • window begins to close when no more all characters in pattern are in window

  • 1
    Y

    @HarryChaoyangHe
    Thanks for the template. For consistency with your template, I rewrite the solution to the problem Substring with Concatenation of All Words.

    public List<Integer> findSubstring(String s, String[] words) {
            if(s == null || s.length() == 0 || words.length == 0) return new ArrayList<Integer>();
            
            int numOfWords = words.length;
            int sLen = s.length();
            int wl = words[0].length();
            
            // 1. construct hashmap
            Map<String, Integer> dict = new HashMap<>();
            for(String word : words) {
                dict.put(word, dict.getOrDefault(word, 0) + 1);
            }
            
            // 2. maintain a sliding window
            List<Integer> res = new ArrayList<>();
            for(int i = 0; i < wl; i++) {
                int begin = i, end = i;
                int counter = 0;
                Map<String, Integer> tdict = new HashMap<>();
                
                while(end <= sLen - wl) {
                    String sub = s.substring(end, end + wl);
                    if(dict.containsKey(sub)) {
                        tdict.put(sub, tdict.getOrDefault(sub, 0) + 1);
                        if(tdict.get(sub) <= dict.get(sub)) {
                            counter++;
                        }
                        end = end + wl;
                        
                        while(tdict.get(sub) > dict.get(sub)) {
                            String tmp = s.substring(begin, begin + wl);
                            if(dict.containsKey(tmp)) {
                                tdict.put(tmp, tdict.get(tmp) - 1);
                                if(tdict.get(tmp) < dict.get(tmp)) {
                                    counter--;
                                }
                            }
                            begin = begin + wl;
                        }
                        
                        if(counter == numOfWords) {
                            res.add(begin);
                            String front = s.substring(begin, begin + wl);
                            tdict.put(front, tdict.get(front) - 1);
                            counter--;
                            begin = begin + wl;
                        }
                    } else {
                        tdict.clear();
                        counter = 0;
                        end = end + wl;
                        begin = end;
                    }
                }
            }
            return res;
        }
    

  • 0
    Z

    OMG it took me a while to fix&improve my code and finally get the point of step //increase begin pointer to make it invalid/valid again........stupid me....


  • 0
    D

    Your idea is so brilliant! Thanks a lot for sharing!


  • 0
    B

    it took me 3 hrs to figure out to use charAt(i) instead of toCharArray()[i], gosh 😂😂


  • 0
    M

    @HarryChaoyangHe You're brilliant! I have only read your template portion and did not even look at the solutions for the specific problems. Then, I went ahead and applied your template to all the questions you mentioned and was able to solve them in a very short amount of time, mostly writing bug-free code. Thank you so much for the very useful post.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.