Sliding Window on Substring

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 general idea is that we can alternatively slide end and begin pointers and stop end once the substr between two pointers satisfies the requirement, then slide begin until breaks the requirement.

  1. Find the first valid substring (move end pointer only)
  2. Slide window to find the shortest valid substring (move both begin and end pointer)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int findSubstring(string s){
unordered_map<char, int> M;
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;
}

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.

Related problems:

Minimum Substring Contains Certain Target String Characters

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

"CDOBACODEBANC","AABC" -> "ACODEBA"

substr sliding window

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
string minWindow(string s, string t) {
// Statistic for count of char in t
unordered_map<char, int> m;
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;
size_t counter = t.size(), size = s.size();
size_t minStart = 0, minLen = INT_MAX;

// 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]]--;

// Move end forward
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 "";
}

#