Substring Problem Template

Example:

Leetcode 76. Minimum Window Substring

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:

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        vector<int> map(128, 0);
        int count = 0, left = 0, right = 0, len = 0;
        while (right < s.size()) {
            if (map[s[right++]]++ == 0) ++count;
            while (count > 2) {
                if (--map[s[left++]] == 0) --count;
            }
            len = max(len, right-left);
        }
        return len;
    }
};

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

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> map(128,0);
        int left = 0, right = 0, maxlen = 0, count = 0;
        while (right < s.size()) {
            if (map[s[right++]]++ > 0) ++count; //invalid
            while (count > 0) { 
                if (map[s[left++]]-- > 1) --count;
            }
            // valid
            maxlen = max(maxlen, right-left);
        }
        return maxlen;
    }
};