10-line template that can solve most “substring” problems

Problem: Leetcode 76. Minimum Window Substring

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The test cases will be generated such that the answer is unique.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

Constraints:

• m == s.length
• n == t.length
• 1 <= m, n <= 10^5
• s and t consist of uppercase and lowercase English letters.

Follow-up: Could you find an algorithm that runs in O (m + n) time?

First, take a look at the solution.

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.

C++ Code:

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.

Here comes the template.

For most substring problems, we are given a string and need to find a substring that satisfies 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 that needs to be mentioned is that when asked to find the maximum substring, we should update the maximum after the inner while loop to guarantee that the substring is valid. On the other hand, when asked to find the minimum substring, we should update the minimum inside the inner while loop.

The code for solving the 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 for solving Longest Substring Without Repeating Characters is below:

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