Here is a 10-line template that can solve most 'substring' problems


  • 1244
    Z

    I will first give the solution then show you the magic template.

    The code of solving this problem is below. It might be the shortest among all solutions provided in Discuss.

    string minWindow(string s, string t) {
            vector<int> map(128,0);
            for(auto c: t) map[c]++;
            int counter=t.size(), begin=0, end=0, d=INT_MAX, head=0;
            while(end<s.size()){
                if(map[s[end++]]-->0) counter--; //in t
                while(counter==0){ //valid
                    if(end-begin<d)  d=end-(head=begin);
                    if(map[s[begin++]]++==0) counter++;  //make it invalid
                }  
            }
            return d==INT_MAX? "":s.substr(head, d);
        }
    

    Here comes the template.

    For most substring problem, we are given a string and need to find a substring of it which satisfy some restrictions. A general way is to use a hashmap assisted with two pointers. The template is given below.

    int findSubstring(string s){
            vector<int> map(128,0);
            int counter; // check whether the substring is valid
            int begin=0, end=0; //two pointers, one point to tail and one  head
            int d; //the length of substring
    
            for() { /* initialize the hash map here */ }
    
            while(end<s.size()){
    
                if(map[s[end++]]-- ?){  /* modify counter here */ }
    
                while(/* counter condition */){ 
                     
                     /* update d here if finding minimum*/
    
                    //increase begin to make it invalid/valid again
                    
                    if(map[s[begin++]]++ ?){ /*modify counter here*/ }
                }  
    
                /* update d here if finding maximum*/
            }
            return d;
      }
    

    One thing needs to be mentioned is that when asked to find maximum substring, we should update maximum after the inner while loop to guarantee that the substring is valid. On the other hand, when asked to find minimum substring, we should update minimum inside the inner while loop.

    The code of solving Longest Substring with At Most Two Distinct Characters is below:

    int lengthOfLongestSubstringTwoDistinct(string s) {
            vector<int> map(128, 0);
            int counter=0, begin=0, end=0, d=0; 
            while(end<s.size()){
                if(map[s[end++]]++==0) counter++;
                while(counter>2) if(map[s[begin++]]--==1) counter--;
                d=max(d, end-begin);
            }
            return d;
        }
    

    The code of solving Longest Substring Without Repeating Characters is below:

    Update 01.04.2016, thanks @weiyi3 for advise.

    int lengthOfLongestSubstring(string s) {
            vector<int> map(128,0);
            int counter=0, begin=0, end=0, d=0; 
            while(end<s.size()){
                if(map[s[end++]]++>0) counter++; 
                while(counter>0) if(map[s[begin++]]-->1) counter--;
                d=max(d, end-begin); //while valid, update d
            }
            return d;
        }
    

    I think this post deserves some upvotes! : )


  • 0
    W
    This post is deleted!

  • 14
    W

    make the template more applicable for Longest Substring Without Repeating Character

    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int len = 0;
        int head = 0, i = 0;
        int[] sTable = new int[256];
        int repeat = 0;
        while (i < s.length()) {
            if (sTable[s.charAt(i++)]++ > 0) repeat++;   //total number of repeat
            while(repeat > 0) {
               if (sTable[s.charAt(head++)]-- > 1) repeat--;
            }
            len = Math.max(len, i - head);
        }
        return len;
    }

  • 0
    Z
    This post is deleted!

  • 2

    Hi, I think your post is the most excellent solution for this problem! Learned a lot from you. Thank you so much!


  • 2
    Z

    Thank you very much. Actually I'm inspired by the solutions here and then find out a general one.


  • 2
    Z

    cool, I love you. Help me a lot, I hope I can get more template from you, haha!


  • 195
    S

    Though your code is short, but code like

    " if(map[s[end++]]++>0) counter++;
    while(counter>0) if(map[s[begin++]]-->1) counter--"

    is barely readable. I will not recommend this kind of code in real work


  • 4
    S

    Nice post. I don't think 'map' is a good choice for variable names though.


  • 14
    G

    Yes, it is hard to read.
    Could any one tell me which is one calculated first in "if(map[s[end++]]++>0) counter++;"? How to rewrite it one line by one line? I am very confused the order. Thanks.


  • 440
    V

    Thanks zjh08177 for this great idea. Let me explain this algorithm.

    1. Use two pointers: start and end to represent a window.
    2. Move end to find a valid window.
    3. When a valid window is found, move start to find a smaller window.
    

    To check if a window is valid, we use a map to store (char, count) for chars in t. And use counter for the number of chars of t to be found in s. The key part is m[s[end]]--;. We decrease count for each char in s. If it does not exist in t, the count will be negative.

    To really understand this algorithm, please see my code which is much clearer, because there is no code like if(map[s[end++]]++>0) counter++;.

    string minWindow(string s, string t) {
    	unordered_map<char, int> m;
    	// Statistic for count of char in t
    	for (auto c : t) m[c]++;
    	// counter represents the number of chars of t to be found in s.
    	size_t start = 0, end = 0, counter = t.size(), minStart = 0, minLen = INT_MAX;
    	size_t size = s.size();
    	
    	// Move end to find a valid window.
    	while (end < size) {
    		// If char in s exists in t, decrease counter
    		if (m[s[end]] > 0)
    			counter--;
    		// Decrease m[s[end]]. If char does not exist in t, m[s[end]] will be negative.
    		m[s[end]]--;
    		end++;
    		// When we found a valid window, move start to find smaller window.
    		while (counter == 0) {
    			if (end - start < minLen) {
    				minStart = start;
    				minLen = end - start;
    			}
    			m[s[start]]++;
    			// When char exists in t, increase counter.
    			if (m[s[start]] > 0)
    				counter++;
    			start++;
    		}
    	}
    	if (minLen != INT_MAX)
    		return s.substr(minStart, minLen);
    	return "";
    }
    

    The code above costs 76ms. If we change the first line unordered_map<char, int> m; to vector<int> m(128, 0);, it costs 12ms.


  • 1
    A

    Based on the above code, and save more space, here is what I got:

    class Solution {
    public:
        string minWindow(string s, string t) {
            unordered_map<char, int> map;
            int count = t.size();
            int begin = 0, end = 0;
            int d = INT_MAX;
            int head = 0;
            for (auto& i: t) map[i]++;
            while (end < s.size()){
                auto foundToPush = map.find(s[end]);
                if (foundToPush != map.end()) if (map[s[end]]-- > 0) count--;
                end++;
    
                while (count == 0){
                    if (end-begin < d) {d = end - begin; head = begin;}
                    auto foundToPop = map.find(s[begin]);
                    if (foundToPop != map.end()) if (map[s[begin]]++ == 0) count++;
                    begin++;
                }
    
            }
            return d == INT_MAX? "": s.substr(head, d);
        }
    };

  • 0
    V

    vector does not use too much space, but it is much faster. If I use unordered_map, it costs 76ms. But if I use vector, it costs only 12ms.


  • -23

  • -9
    9

  • -8
    9

  • 1
    M

    I think it's better to explain the "start" pointer in this way:
    We want to find the minimum legal substr which begin at "start" pointer, when the substr is smaller than current minimum ,update the minimum.
    I think it is a greedy solution.


  • 3
    M

    Well I learn and understand this solution. However, doesn't this create some suspicion of memorising solutions in interview ? I clearly understand it and probably solve anything similar in extreme speed because of this. Doesn't that makes me someone memorising solutions from the perspective of interviewer ?


  • 2
    Z

    I want to point out that although the code "if(map[s[end++]]++>0) counter++" is not as easy to read as writing line by line, the efficiency of this writing style is better than writing line by line. Because writing line by line will cause extra access for hashmap(here vector or array). Actually, if you understand the difference between i++ and ++i, it's not difficult to read the code. Just understand it and get used to it.


  • 1
    B

    By far the most impressing explanation I saw in LC.


Log in to reply
 

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