School A: Already satisfies the condition, any bigger is redundant → shrink when satisfied#

Representative problems: Minimum Window Substring (already covers t), Permutation in String / Find All Anagrams (length has reached |s1|).

1
while (valid == need.size())      // The window already covers the target; continuing to expand would only make it longer
2
while (right - left >= len1)      // The window length has already reached the pattern string length; any longer cannot be a permutation

The window in these problems is “the bigger, the easier to satisfy”: the wider the window, the more chances to cover the target characters. So once satisfied, it means “the current right boundary doesn’t need to go further; we only need to consider whether the left boundary can tighten a bit more,” and shrinking begins immediately.

The latter two conditions right - left >= len1 are essentially a fixed-length window: shrink once the length is reached, ensuring the window length is always exactly len1. This is also why “Permutation in String” and “Find All Anagrams” are essentially the same problem — both use a fixed-length window + count verification.

School B: Already violates the condition → shrink when violated#

Representative problem: Longest Substring Without Repeating Characters.

1
while (win[c] > 1)                // the newly added c is duplicated in the window, must shrink until no duplicates

The window in these problems is “the smaller, the easier to satisfy”: the narrower the window, the less likely a duplicate appears. So after expanding, you first check whether it violates the condition, and once it does, shrink all the way until it’s valid again.

The conditions for both schools are written in the same while, but the semantics are completely opposite: one is “it’s already good, try asking for a little less,” and the other is “it’s already broken, shrink until it’s good.” Before writing code, figure out which school the problem belongs to, and the shrink condition writes itself.

Problem Description#

Given a string s and a string t, return the minimum substring of s that covers all characters in t. If no substring in s covers all characters in t, return the empty string "".

Note: For duplicate characters in t, the count of that character in the substring we seek must be no less than the count of that character in t.

Example:

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

5
Input: s = "a", t = "a"     Output: "a"
6
Input: s = "a", t = "aa"    Output: ""

Constraints: 1 <= m, n <= 10^5 (m == s.length, n == t.length), s and t consist of uppercase and lowercase English letters, and the test cases guarantee a unique answer.

Three Questions#

The three answers for this problem

1. When to expand right: Expand unconditionally. When adding c, if c belongs to t, increment win[c]; when win[c] exactly equals need[c], increment valid (indicating one more character has met the requirement).
2. When to shrink left: Start shrinking when valid == need.size(), that is, “the window has already covered all characters of t.” When removing d, if d just drops from “meeting the requirement” (win[d] == need[d]), first decrement valid, then decrement win[d].
3. When to update the result: Inside the shrink loop, before removal — at this point the window exactly “just covers t,” which is precisely the shortest candidate we want. The order must be record first, then remove.

Process Walkthrough#

Using s = "ADOBECODEBANC" and t = "ABC" as an example (need: A=1, B=1, C=1, need.size() == 3):

1
s = A D O B E C O D E B A N C
2
    0 1 2 3 4 5 6 7 8 9 10 11 12
3

4
Add A → valid = 1
5
Add B → valid = 2
6
Add C → valid = 3   ← window [0,6) = "ADOBEC" already covers t, enter the shrink loop
7
  ├ First record the answer: [0,6) length 6 → minLen = 6 (tentatively "ADOBEC")
8
  └ Then remove s[0]='A' → A no longer meets the requirement → valid = 2 → exit shrink
9

10
…… right continues expanding to 11 (window [1,11)), A meets the requirement again → valid = 3
11
   In the shrink loop the lengths are 10, 9, 8, 7, 6 in order, none better than 6, so the answer is not updated
12

13
Add C (index 12) → valid = 3, window [6,13) = "ODEBANC" length 7
14
  ├ Length 7 > 6, do not update
15
  ├ Remove O (not in t, valid unchanged) → window [7,13) = "DEBANC" length 6, still not better
16
  ├ Remove D again → window [8,13) = "EBANC" length 5 → refresh minLen = 5
17
  ├ Remove E → window [9,13) = "BANC" length 4 → refresh minLen = 4
18
  └ Remove B → B no longer meets the requirement → valid = 2 → exit shrink
19

20
Answer "BANC" ✔

Note a detail in the second step: in window [3,11) = "BECODEBA", B appears twice, win[B] = 2 > need[B] = 1. At this point, after removing one B, win[B] drops to 1 and still meets the requirement, so valid should not change. The code checks win[d] == need[d] (not meeting the requirement only after removal) rather than win[d] <= need[d], precisely to handle this case.

Code Implementation#

1
#include <stdlib.h>
2
#include <string.h>
3

4
char *minWindow(char *s, char *t) {
5
    int need[128] = {0}, win[128] = {0};   /* need: target counts; win: window counts */
6
    int needKinds = 0;                     /* how many distinct characters are in the target */
7
    for (int i = 0; t[i] != '\0'; i++) {
8
        if (need[(unsigned char)t[i]] == 0) needKinds++;
9
        need[(unsigned char)t[i]]++;
10
    }
11

12
    int left = 0, right = 0;
13
    int valid = 0;                         /* how many distinct characters have reached the required count */
14
    int start = 0, minLen = -1;
15
    int n = (int)strlen(s);
16

17
    while (right < n) {
18
        char c = s[right];                 /* 1. character about to enter the window */
19
        right++;                           /* 2. expand the window to the right */
20
        if (need[(unsigned char)c] > 0) {  /* 3. update the data inside the window */
21
            win[(unsigned char)c]++;
22
            if (win[(unsigned char)c] == need[(unsigned char)c]) valid++;
23
        }
24

25
        while (valid == needKinds) {       /* 4. the window already covers t, start shrinking */
26
            if (minLen == -1 || right - left < minLen) {   /* record the answer first, then remove */
27
                start = left;
28
                minLen = right - left;
29
            }
30
            char d = s[left];              /* 5. remove left */
31
            left++;
32
            if (need[(unsigned char)d] > 0) {
33
                if (win[(unsigned char)d] == need[(unsigned char)d]) valid--;
34
                win[(unsigned char)d]--;
35
            }
36
        }
37
    }
38

39
    char *res = (char *)malloc(minLen < 0 ? 1 : minLen + 1);
40
    if (minLen < 0) {
41
        res[0] = '\0';
42
    } else {
43
        memcpy(res, s + start, minLen);
44
        res[minLen] = '\0';
45
    }
46
    return res;
47
}

1
#include <string>
2
#include <vector>
3
using namespace std;
4

5
class Solution {
6
public:
7
    string minWindow(string s, string t) {
8
        int need[128] = {0}, win[128] = {0};   // need: target counts; win: window counts
9
        int needKinds = 0;                      // how many distinct characters are in the target
10
        for (char c : t) {
11
            if (need[(unsigned char)c] == 0) ++needKinds;
12
            ++need[(unsigned char)c];
13
        }
14

15
        int left = 0, right = 0;
16
        int valid = 0;                          // how many distinct characters have reached the required count
17
        int start = 0, minLen = -1;
18

19
        while (right < (int)s.size()) {
20
            char c = s[right];                  // 1. character about to enter the window
21
            ++right;                            // 2. expand the window to the right
22
            if (need[(unsigned char)c] > 0) {   // 3. update the data inside the window
23
                ++win[(unsigned char)c];
24
                if (win[(unsigned char)c] == need[(unsigned char)c]) ++valid;
25
            }
26

27
            while (valid == needKinds) {        // 4. the window already covers t, start shrinking
28
                if (minLen == -1 || right - left < minLen) {   // record the answer first
29
                    start = left;
30
                    minLen = right - left;
31
                }
32
                char d = s[left];               // 5. remove left
33
                ++left;
34
                if (need[(unsigned char)d] > 0) {
35
                    if (win[(unsigned char)d] == need[(unsigned char)d]) --valid;
36
                    --win[(unsigned char)d];
37
                }
38
            }
39
        }
40
        return minLen == -1 ? "" : s.substr(start, minLen);
41
    }
42
};

1
function minWindow(s, t) {
2
  const need = new Map();                 // need: target counts
3
  for (const c of t) need.set(c, (need.get(c) ?? 0) + 1);
4

5
  const win = new Map();                  // win: window counts
6
  let left = 0;
7
  let right = 0;
8
  let valid = 0;                          // how many distinct characters have reached the required count
9
  let start = 0;
10
  let minLen = Infinity;
11

12
  while (right < s.length) {
13
    const c = s[right];                   // 1. character about to enter the window
14
    right++;                              // 2. expand the window to the right
15
    if (need.has(c)) {                    // 3. update the data inside the window
16
      win.set(c, (win.get(c) ?? 0) + 1);
17
      if (win.get(c) === need.get(c)) valid++;
18
    }
19

20
    while (valid === need.size) {         // 4. the window already covers t, start shrinking
21
      if (right - left < minLen) {        // record the answer first, then remove
22
        start = left;
23
        minLen = right - left;
24
      }
25
      const d = s[left];                  // 5. remove left
26
      left++;
27
      if (need.has(d)) {
28
        if (win.get(d) === need.get(d)) valid--;
29
        win.set(d, win.get(d) - 1);
30
      }
31
    }
32
  }
33

34
  return minLen === Infinity ? "" : s.slice(start, start + minLen);
35
}

Complexity#

Common Pitfalls#

1. Recording the answer must happen before removing left. Placing it on the second line of the loop would record a window that no longer covers t.
2. The check for valid must use win[d] == need[d], not <=. A character in the window may be in excess (such as the two B in the walkthrough above); when dropping from excess to exactly meeting the requirement, valid should not change.
3. Duplicate characters in t must be counted by quantity. s = "a", t = "aa" must return "", which is guaranteed by the exact comparison of win[c] == need[c].
4. Using a fixed-size array instead of a hash table saves constants. s and t contain only uppercase and lowercase letters (52 types), so int[128] is completely sufficient — faster and more memory-efficient than a Map.

Problem Description#

Given two strings s1 and s2, write a function to determine whether s2 contains a permutation of s1. If so, return true; otherwise, return false. In other words, one of the permutations of s1 is a substring of s2.

Example:

1
Input: s1 = "ab", s2 = "eidbaooo"      Output: true
2
Explanation: s2 contains one permutation of s1 ("ba")
3

4
Input: s1 = "ab", s2 = "eidboaoo"      Output: false

Constraints: 1 <= s1.length, s2.length <= 10^4, s1 and s2 consist of lowercase English letters only.

Three Questions#

The three answers for this problem

1. When to expand right: Expand unconditionally. The maintained data is exactly the same as the previous problem: win[c] and valid.
2. When to shrink left: Shrink when right - left >= s1.size() — the window length has already reached |s1|, and any longer would make it absolutely impossible to be a permutation. This is a fixed-length window.
3. When to update the result: Return as soon as it hits. The check is written inside the shrink loop, before removal: at this moment the window length is exactly |s1|, and as long as valid == need.size(), it means the character counts in the window match s1 exactly.

Walkthrough#

Taking s1 = "ab" and s2 = "eidbaooo" as an example:

1
s2 = e i d b a o o o
2
     0 1 2 3 4 5 6 7      s1 = "ab" → need: a=1, b=1, kinds=2
3

4
Add e → window [0,1)="e"  valid=0
5
Add i → window [0,2)="ei" valid=0
6
  length 2 has reached |s1| → check valid(0) != 2 → no hit, remove 'e' → window [1,2)
7
Add d → window [1,3)="id" valid=0 → check no hit, remove 'i' → window [2,3)
8
Add b → window [2,4)="db" valid=1 → check no hit, remove 'd' → window [3,4)
9
Add a → window [3,5)="ba" valid=2 → check valid == kinds hit → return true ✔

The window length is strictly pinned to 2 by right - left >= s1.size(), so each round checks a window of “exactly length |s1|” — this is precisely the fixed-length window approach.

Code Implementation#

1
#include <string.h>
2

3
int checkInclusion(char *s1, char *s2) {
4
    int need[128] = {0}, win[128] = {0};
5
    int needKinds = 0;
6
    for (int i = 0; s1[i] != '\0'; i++) {
7
        if (need[(unsigned char)s1[i]] == 0) needKinds++;
8
        need[(unsigned char)s1[i]]++;
9
    }
10

11
    int left = 0, right = 0, valid = 0;
12
    int len1 = (int)strlen(s1), len2 = (int)strlen(s2);
13

14
    while (right < len2) {
15
        char c = s2[right];
16
        right++;
17
        if (need[(unsigned char)c] > 0) {
18
            win[(unsigned char)c]++;
19
            if (win[(unsigned char)c] == need[(unsigned char)c]) valid++;
20
        }
21

22
        while (right - left >= len1) {     /* the window cannot grow any longer */
23
            if (valid == needKinds) return 1;
24
            char d = s2[left];
25
            left++;
26
            if (need[(unsigned char)d] > 0) {
27
                if (win[(unsigned char)d] == need[(unsigned char)d]) valid--;
28
                win[(unsigned char)d]--;
29
            }
30
        }
31
    }
32
    return 0;
33
}

1
#include <string>
2
using namespace std;
3

4
class Solution {
5
public:
6
    bool checkInclusion(string s1, string s2) {
7
        int need[128] = {0}, win[128] = {0};
8
        int needKinds = 0;
9
        for (char c : s1) {
10
            if (need[(unsigned char)c] == 0) ++needKinds;
11
            ++need[(unsigned char)c];
12
        }
13

14
        int left = 0, right = 0, valid = 0;
15

16
        while (right < (int)s2.size()) {
17
            char c = s2[right];
18
            ++right;
19
            if (need[(unsigned char)c] > 0) {
20
                ++win[(unsigned char)c];
21
                if (win[(unsigned char)c] == need[(unsigned char)c]) ++valid;
22
            }
23

24
            while (right - left >= (int)s1.size()) {   // the window cannot grow any longer
25
                if (valid == needKinds) return true;
26
                char d = s2[left];
27
                ++left;
28
                if (need[(unsigned char)d] > 0) {
29
                    if (win[(unsigned char)d] == need[(unsigned char)d]) --valid;
30
                    --win[(unsigned char)d];
31
                }
32
            }
33
        }
34
        return false;
35
    }
36
};

1
function checkInclusion(s1, s2) {
2
  const need = new Map();
3
  for (const c of s1) need.set(c, (need.get(c) ?? 0) + 1);
4

5
  const win = new Map();
6
  let left = 0;
7
  let right = 0;
8
  let valid = 0;
9

10
  while (right < s2.length) {
11
    const c = s2[right];
12
    right++;
13
    if (need.has(c)) {
14
      win.set(c, (win.get(c) ?? 0) + 1);
15
      if (win.get(c) === need.get(c)) valid++;
16
    }
17

18
    while (right - left >= s1.length) {   // the window cannot grow any longer
19
      if (valid === need.size) return true;
20
      const d = s2[left];
21
      left++;
22
      if (need.has(d)) {
23
        if (win.get(d) === need.get(d)) valid--;
24
        win.set(d, win.get(d) - 1);
25
      }
26
    }
27
  }
28
  return false;
29
}

Complexity#

Common Pitfalls#

1. The shrink condition is >=, not ==. Use while instead of if to ensure the window length strictly does not exceed |s1|; writing == will miss the shrink under certain inputs.
2. The hit check goes inside the shrink loop, before removal. Once you remove first, the window length is no longer |s1|.
3. Don’t try to enumerate all permutations of s1. When |s1| = 10^4, the number of permutations is astronomical; you must replace “enumerating permutations” with “equal counts.”
4. When s1 is longer than s2, return false directly. This boundary case is handled automatically by the code above (the loop condition fails from the start), but make sure you haven’t done any out-of-bounds access outside the loop.

Problem Description#

Given two strings s and p, find all substrings in s that are anagrams of p, and return the starting indices of these substrings. The order of the output does not matter.

An anagram is a string formed by rearranging the same letters (including identical strings).

Example:

1
Input: s = "cbaebabacd", p = "abc"
2
Output: [0,6]
3
Explanation:
4
The substring with starting index equal to 0 is "cba", which is an anagram of "abc".
5
The substring with starting index equal to 6 is "bac", which is an anagram of "abc".
6

7
Input: s = "abab", p = "ab"
8
Output: [0,1,2]

Constraints: 1 <= s.length, p.length <= 3 * 10^4, s, and p consist of lowercase English letters only.

Three Questions#

The three answers for this problem

1. When to expand right: Expand unconditionally, maintaining win[c] and valid—exactly the same as the previous two problems.
2. When to shrink left: It is also a fixed-length window; shrink when right - left >= p.size().
3. When to update the result: On a hit, do not return; instead, collect the current left. The position is still inside the shrink loop, before removal, where the window length is exactly |p| and valid == need.size().

In other words, this problem differs from Problem 567 by only one action: on a hit, 567 does return true, while 438 does res.push(left) and then continues scanning. Placing the code for both problems side by side, they are nearly identical except for this one line—this is exactly the point of a “template”: recognize a class of problems, and you can reuse the entire skeleton.

Process Walkthrough#

Using s = "cbaebabacd" and p = "abc" as an example (need: a=1, b=1, c=1, kinds = 3):

1
s = c b a e b a b a c d
2
    0 1 2 3 4 5 6 7 8 9
3

4
The window length is always 3 (shrink when right - left >= 3), check one by one:
5

6
Window [0,3) = "cba" → valid=3 → collect left=0 ✔
7
Window [1,4) = "bae" → 'e' does not belong to p, valid < 3 → skip
8
Window [2,5) = "aeb" → skip
9
Window [3,6) = "eba" → skip
10
Window [4,7) = "bab" → b exceeds the limit, valid < 3 → skip
11
Window [5,8) = "aba" → skip
12
Window [6,9) = "bac" → valid=3 → collect left=6 ✔
13
Window [7,10) = "acd" → skip
14

15
Return [0, 6] ✔

Code Implementation#

1
#include <stdlib.h>
2
#include <string.h>
3

4
int *findAnagrams(char *s, char *p, int *returnSize) {
5
    int need[128] = {0}, win[128] = {0};
6
    int needKinds = 0;
7
    for (int i = 0; p[i] != '\0'; i++) {
8
        if (need[(unsigned char)p[i]] == 0) needKinds++;
9
        need[(unsigned char)p[i]]++;
10
    }
11

12
    int left = 0, right = 0, valid = 0;
13
    int n = (int)strlen(s), lenP = (int)strlen(p);
14

15
    int *res = (int *)malloc(sizeof(int) * (n + 1));   /* at most n answers */
16
    *returnSize = 0;
17

18
    while (right < n) {
19
        char c = s[right];
20
        right++;
21
        if (need[(unsigned char)c] > 0) {
22
            win[(unsigned char)c]++;
23
            if (win[(unsigned char)c] == need[(unsigned char)c]) valid++;
24
        }
25

26
        while (right - left >= lenP) {
27
            if (valid == needKinds) res[(*returnSize)++] = left;   /* collect the starting point */
28
            char d = s[left];
29
            left++;
30
            if (need[(unsigned char)d] > 0) {
31
                if (win[(unsigned char)d] == need[(unsigned char)d]) valid--;
32
                win[(unsigned char)d]--;
33
            }
34
        }
35
    }
36
    return res;
37
}

1
#include <string>
2
#include <vector>
3
using namespace std;
4

5
class Solution {
6
public:
7
    vector<int> findAnagrams(string s, string p) {
8
        int need[128] = {0}, win[128] = {0};
9
        int needKinds = 0;
10
        for (char c : p) {
11
            if (need[(unsigned char)c] == 0) ++needKinds;
12
            ++need[(unsigned char)c];
13
        }
14

15
        int left = 0, right = 0, valid = 0;
16
        vector<int> res;
17

18
        while (right < (int)s.size()) {
19
            char c = s[right];
20
            ++right;
21
            if (need[(unsigned char)c] > 0) {
22
                ++win[(unsigned char)c];
23
                if (win[(unsigned char)c] == need[(unsigned char)c]) ++valid;
24
            }
25

26
            while (right - left >= (int)p.size()) {
27
                if (valid == needKinds) res.push_back(left);
28
                char d = s[left];
29
                ++left;
30
                if (need[(unsigned char)d] > 0) {
31
                    if (win[(unsigned char)d] == need[(unsigned char)d]) --valid;
32
                    --win[(unsigned char)d];
33
                }
34
            }
35
        }
36
        return res;
37
    }
38
};

1
function findAnagrams(s, p) {
2
  const need = new Map();
3
  for (const c of p) need.set(c, (need.get(c) ?? 0) + 1);
4

5
  const win = new Map();
6
  const res = [];
7
  let left = 0;
8
  let right = 0;
9
  let valid = 0;
10

11
  while (right < s.length) {
12
    const c = s[right];
13
    right++;
14
    if (need.has(c)) {
15
      win.set(c, (win.get(c) ?? 0) + 1);
16
      if (win.get(c) === need.get(c)) valid++;
17
    }
18

19
    while (right - left >= p.length) {
20
      if (valid === need.size) res.push(left);
21
      const d = s[left];
22
      left++;
23
      if (need.has(d)) {
24
        if (win.get(d) === need.get(d)) valid--;
25
        win.set(d, win.get(d) - 1);
26
      }
27
    }
28
  }
29
  return res;
30
}

Complexity#

Common Pitfalls#

1. Collect left, not right. The window is [left, right), and the starting index is left.
2. Do not exit early after collecting. This is the only difference from 567: 567 only needs to determine existence, while 438 must enumerate all.
3. Duplicate answers and order. The same starting point is only checked once; the problem does not require order, and push naturally produces ascending order.

Problem Description#

Given a string s, find the length of the longest substring that does not contain repeating characters.

Example:

1
Input: s = "abcabcbb"    Output: 3
2
Explanation: Because the longest substring without repeating characters is "abc", its length is 3.
3

4
Input: s = "bbbbb"       Output: 1
5
Explanation: Because the longest substring without repeating characters is "b", its length is 1.
6

7
Input: s = "pwwkew"      Output: 3
8
Explanation: Because the longest substring without repeating characters is "wke", its length is 3.
9
     Note that the answer must be a substring; "pwke" is a subsequence, not a substring.

Constraints: 0 <= s.length <= 5 * 10^4, s consists of English letters, digits, symbols, and spaces.

Three Questions#

The three answers for this problem

1. When to expand right: Expand unconditionally. After adding c, only one piece of state needs to be maintained: the win[c] count (used to detect duplicates).
2. When to shrink left: Shrink when win[c] > 1, and keep shrinking until win[c] == 1. Here the window is easier to keep valid the smaller it is, so this belongs to the “shrink on violation” camp.
3. When to update the result: After the shrink loop. At that point the window [left, right) is duplicate-free, so use right - left to update the maximum.

Note that the third question is exactly the opposite of the previous three problems. The state needed in the previous three is “exactly covers / length exactly k,” which is destroyed as soon as you shrink, so you must record before shrinking; the state needed here is “no duplicates,” and before shrinking the window may still be in a violating state, so you must wait until shrinking ends and the window is fixed before recording.

The consequence of using the wrong order: if you put the best update before shrinking, "abcabcbb" will at some point count a window like "abca" that contains duplicate characters, yielding the wrong answer of 4.

Process Walkthrough#

Taking s = "abcabcbb" as an example:

1
s = a b c a b c b b
2
    0 1 2 3 4 5 6 7
3

4
Add a (index 0) → window [0,1) = "a"     no violation → best = 1
5
Add b (index 1) → window [0,2) = "ab"    no violation → best = 2
6
Add c (index 2) → window [0,3) = "abc"   no violation → best = 3
7
Add a (index 3) → window [0,4) = "abca"  a appears 2 times → remove 'a' → window [1,4) = "bca" length 3, not better
8
Add b (index 4) → window [1,5) = "bcab"  b appears 2 times → remove 'b' → window [2,5) = "cab" length 3, not better
9
Add c (index 5) → window [2,6) = "cabc"  c appears 2 times → remove 'c' → window [3,6) = "abc" length 3, not better
10
Add b (index 6) → window [3,7) = "abcb"  b appears 2 times
11
   → remove 'a' → window [4,7) = "bcb", b still repeats
12
   → remove 'b' → window [5,7) = "cb"  length 2, not better
13
Add b (index 7) → window [5,8) = "cbb"  b appears 2 times
14
   → remove 'c' → window [6,8) = "bb", b still repeats
15
   → remove 'b' → window [7,8) = "b"   length 1, not better
16

17
Answer = 3 ✔

The c in while (win[c] > 1) is always the character just added: within the window, only it can become duplicated due to the new addition; all other characters were duplicate-free at the end of the previous round. So the shrink target is very clear — squeeze out the extra c.

Code Implementation#

1
#include <string.h>
2

3
int lengthOfLongestSubstring(char *s) {
4
    int win[128] = {0};                  /* occurrence count of each character in the window */
5
    int left = 0, right = 0, best = 0;
6
    int n = (int)strlen(s);
7

8
    while (right < n) {
9
        char c = s[right];
10
        right++;
11
        win[(unsigned char)c]++;                 /* 3. update the data inside the window */
12

13
        while (win[(unsigned char)c] > 1) {      /* 4. violation: there is a duplicate, shrink */
14
            char d = s[left];
15
            left++;
16
            win[(unsigned char)d]--;
17
        }
18

19
        if (right - left > best) best = right - left;   /* 5. update the answer only after shrinking */
20
    }
21
    return best;
22
}

1
#include <string>
2
using namespace std;
3

4
class Solution {
5
public:
6
    int lengthOfLongestSubstring(string s) {
7
        int win[128] = {0};          // occurrence count of each character in the window
8
        int left = 0, right = 0, best = 0;
9

10
        while (right < (int)s.size()) {
11
            char c = s[right];
12
            ++right;
13
            ++win[(unsigned char)c];              // 3. update the data inside the window
14

15
            while (win[(unsigned char)c] > 1) {   // 4. violation: there is a duplicate, shrink
16
                char d = s[left];
17
                ++left;
18
                --win[(unsigned char)d];
19
            }
20

21
            if (right - left > best) best = right - left;   // 5. update the answer only after shrinking
22
        }
23
        return best;
24
    }
25
};

1
function lengthOfLongestSubstring(s) {
2
  const win = new Map();                  // occurrence count of each character in the window
3
  let left = 0;
4
  let right = 0;
5
  let best = 0;
6

7
  while (right < s.length) {
8
    const c = s[right];
9
    right++;
10
    win.set(c, (win.get(c) ?? 0) + 1);    // 3. update the data inside the window
11

12
    while (win.get(c) > 1) {              // 4. violation: there is a duplicate, shrink
13
      const d = s[left];
14
      left++;
15
      win.set(d, win.get(d) - 1);
16
    }
17

18
    best = Math.max(best, right - left);  // 5. update the answer only after shrinking
19
  }
20
  return best;
21
}

Complexity#

Common Pitfalls#

1. The position of the answer update. It must be after the while shrink loop; this is the biggest difference between this problem and the previous three.
2. The shrink loop checks the character just added, c, not s[left]. Because only c can be duplicated.
3. s may be empty. When s.length == 0, the loop does not execute and returns 0, so no special handling is needed; but the initialization of best = 0 must be written correctly.
4. Do not use something like s.indexOf(c, left) to jump left directly. Although that approach is faster, it departs from the template and easily fails on other problems. The value of the template lies in uniformity; first make sure you can write the template version, then consider optimizing.