Sliding Window, a popular method in programming problems, surprisingly, shares the same idea with Binary Search. In this post, we will show that Sliding Window is a 2D extension of Binary Search. We will also find that solving Sliding Window problems is nothing more than searching the 01 boundaries in 2D space.

This post is the second post of the【01Boundary】series.

We first model the two situtations of Sliding Window, Max Window and Min Window, with the state $(i, j)$ and the binary predicate $\text{Pred}(i, j)$ .
Then, we talk about four popular problems (minimum length window, maximum length window, min counting, and max counting) under the model.
After that, we derive the duality of Max Window and Min Window. Then we prove that we could transform Max Window to Min Window by negating the predicate $\text{Pred}(i, j)$ .
At the end of the introduction, we provide a code template for Min Window.
In the Selected Problem section, we mainly focus on two types of problems:
- Max/Min Window Problems
  - Leetcode 76 Minimum Window Substring
  - Leetcode 632 Smallest Range Covering Elements from K Lists
  - … and other 6 problems.
- Subarray Counting Problems
  - Leetcode 1248 Count Number of Nice Subarrays
  - Leetcode 1918 Kth Smallest Subarray Sum
  - … and other 3 problems.

Keywords for sliding window problems:
longest/shortest subarray/substring, maximum/minimum length subarray/substring, number of such subarray.

Introduction

Min Window

Define the state $s = (i, j)$, $0 \leq i \leq j < N$.

Define the binary predicate $\text{Pred}$ as a function on the space of the state $s$.

Property 1: For all $j \in [0, N)$, There exists one and only one $i_{m} \in [0, j)$, such that:

$\forall i \in [0, i_{m})$, $\text{Pred}(i, j) = 1$
$\forall i \in [i_{m}, j)$, $\text{Pred}(i, j) = 0$

Property 2: For all $i \in [0, N)$, There exists one and only one $j_{m} \in [i, N)$, such that:

$\forall j \in [i, j_{m})$, $\text{Pred}(i, j) = 0$
$\forall j \in [j_{m}, N)$, $\text{Pred}(i, j) = 1$

                              j = 13, im = 11
                              i = 6, jm = 13
                              ▲
                              │
                 ┌─┬─┬─┬─┬─┬─┬┴┬─┬─┬─┬─┬─┬─┬─┐
               13│1│1│1│1│1│1│1│1│1│1│1│0│0│0│
                 ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘
j = 11, im = 6 12│1│1│1│1│1│1│0│0│0│0│0│0│0│1
i = 2, jm = 11   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘3
         ◄─────11│1│1│1│1│1│1│0│0│0│0│0│0│1
                 ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘2
               10│1│0│0│0│0│0│0│0│0│0│0│1
                 ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘1
                9│1│0│0│0│0│0│0│0│0│0│1
                 ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘0
                8│1│0│0│0│0│0│0│0│0│9
                 ├─┼─┼─┼─┼─┼─┼─┼─┼─┘
 j = 6, im = 1  7│1│0│0│0│0│0│0│0│8
 i = 0, jm = 6   ├─┼─┼─┼─┼─┼─┼─┼─┘
         ◄───── 6│1│0│0│0│0│0│0│7
                 ├─┼─┼─┼─┼─┼─┼─┘
                5│0│0│0│0│0│0│6
                 ├─┼─┼─┼─┼─┼─┘
                4│0│0│0│0│0│5
                 ├─┼─┼─┼─┼─┘
                3│0│0│0│0│4
                 ├─┼─┼─┼─┘
                2│0│0│0│3
                 ├─┼─┼─┘
                1│0│0│2
                 ├─┼─┘
                0│0│1
                 └─┘
                  0

Take this figure as an example. The value of every $\text{Pred}(i, j)$ is shown in the figure at its position $(i, j)$. As a result of Property 1 and Property 2, we could observe the following two situations.

If we fix $i$ and increase $j$, once $\text{Pred}(i, j)$ becomes $1$, it will remain $1$ as we continue increasing $j$.
Similarly, If we fix $j$ and increase $i$, once $\text{Pred}(i, j)$ becomes $0$, it will remain $0$ as we continue increasing $i$.

Now consider the following two problems:

PROBLEM1: Find $\min(j - i)$, such that $0 \leq i < j < N$ and $\text{Pred}(i, j) = 1$

PROBLEM2: Find the number of states $s = (i, j)$, such that $0 \leq i < j < N$ and $\text{Pred}(i, j) = 1$.

For the first problem, it is equivalent to finding $m_{i} = \displaystyle\min_{j}(j - i)$ for every $i$ . Then we simply take the minimum of all such $m_{i}$ .

It could be observed from the figure that for each $i$ , the smallest $j$ that makes $\text{Pred}(i, j) = 1$ is exactly $j_m$ in Property 2.

All $j \geq j_m$ has $\text{Pred}(i, j) = 1$ , all $j < j_m$ has $\text{Pred}(i, j) = 0$ .
When $i$ is fixed, $j_m$ is the smallest possible $j$ that has $\text{Pred}(i, j) = 1$ .
That is, $j_m$ minimizes $j - i$ for each $i$ , such that $\text{Pred}(i, j) = 1$ .
Therefore, for each $i$ , once $j$ has reached $j_m$ , there is no need to increase $j$ anymore.

When we have reached $j_m$ , we could fix $j$ and increase $i$ , which makes $j - i$ smaller. From Property 1, we know that there will be some $i_m$ that makes $\text{Pred}(i_m, j) = 0$ .

Once we has visited $(i_m, j)$ , then fix $i = i_m$ and increase $j$ again. We keep doing this until we reach the final state $(N, N)$ .

We could observe that for each $i$ , every corresponding $j_m$ is visited when we have reached the final state. Thus, we could find $m_{i} = \displaystyle\min_{j}(j - i) = j_m - i$ for each $i$ . Then we take $m = \displaystyle \min_{i} m_i$ as the result of the problem.

For the second problem, we visit $(i, j_m)$ for each $i$ in the same way as the first problem. For each $(i, j_m)$ , we know that all $j \geq j_m$ have $\text{Pred}(i, j) = 1$ . Therefore, for each $i$ , there are $N - j_m$ states that have $\text{Pred}(i, j) = 1$ . We could sum $N - j_m$ for each $i$ together to get the result.

The transition of state $(i, j)$ is shown in the figure below. $(i, j)$ starts at $(0, 0)$ and ends at $(11, 13)$ .

                              j = 13, im = 11                               j = 13, im = 11
                              i = 6, jm = 13                                i = 6, jm = 13
                              ▲                                             ▲
                              │                                             │
                 ┌─┬─┬─┬─┬─┬─┬┴──────────┬─┬─┐                 ┌─┬─┬─┬─┬─┬─┬┴┬─┬─┬─┬─┬─┬─┬─┐
               13│1│1│1│1│1│1│xxxxxxxxxxx│0│0│               13│1│1│1│1│1│1│1│1│1│1│1│0│0│0│
                 ├─┼─┼─┼─┼─┼─┤x┌─┬─┬─┬─┬─┼─┼─┘                 ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘
j = 11, im = 6 12│1│1│1│1│1│1│x│0│0│0│0│0│0│1 j = 11, im = 6 12│1│1│1│1│1│1│0│0│0│0│0│0│0│1
i = 2, jm = 11   ├─┼─┴─┴─┴─┴─┘x├─┼─┼─┼─┼─┼─┘3 i = 2, jm = 11   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘3
         ◄─────11│1│xxxxxxxxxxx│0│0│0│0│0│1            ◄─────11│1│1│1│1│1│1│0│0│0│0│0│0│1
                 ├─┤x┌─┬─┬─┬─┬─┼─┼─┼─┼─┼─┘2                    ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘2
               10│1│x│0│0│0│0│0│0│0│0│0│1                    10│1│0│0│0│0│0│0│0│0│0│0│1
                 ├─┤x├─┼─┼─┼─┼─┼─┼─┼─┼─┘1                      ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘1
                9│1│x│0│0│0│0│0│0│0│0│1                       9│1│0│0│0│0│0│0│0│0│0│1
                 ├─┤x├─┼─┼─┼─┼─┼─┼─┼─┘0                        ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘0
                8│1│x│0│0│0│0│0│0│0│9                         8│1│0│0│0│0│0│0│0│0│9
                 ├─┤x├─┼─┼─┼─┼─┼─┼─┘                           ├─┼─┼─┼─┼─┼─┼─┼─┼─┘
 j = 6, im = 1  7│1│x│0│0│0│0│0│0│8            j = 6, im = 1  7│1│0│0│0│0│0│0│0│8
 i = 0, jm = 6   ├─┘x├─┼─┼─┼─┼─┼─┘             i = 0, jm = 6   ├─┼─┼─┼─┼─┼─┼─┼─┘
         ◄───── 6│xxx│0│0│0│0│0│7                      ◄───── 6│1│0│0│0│0│0│0│7
                 │x┌─┼─┼─┼─┼─┼─┘                               ├─┼─┼─┼─┼─┼─┼─┘
                5│x│0│0│0│0│0│6                               5│0│0│0│0│0│0│6
                 │x├─┼─┼─┼─┼─┘                                 ├─┼─┼─┼─┼─┼─┘
                4│x│0│0│0│0│5                                 4│0│0│0│0│0│5
                 │x├─┼─┼─┼─┘                                   ├─┼─┼─┼─┼─┘
                3│x│0│0│0│4                                   3│0│0│0│0│4
                 │x├─┼─┼─┘                                     ├─┼─┼─┼─┘
                2│x│0│0│3                                     2│0│0│0│3
                 │x├─┼─┘                                       ├─┼─┼─┘
                1│x│0│2                                       1│0│0│2
                 │x├─┘                                         ├─┼─┘
                0│x│1                                         0│0│1
                 └─┘                                           └─┘
                  0                                             0

Max Window

Let us consider another situation when we negate the binary predicate $\text{Pred}$ in Property 1 and Property 2.

Define the state $s = (i, j)$, $0 \leq i \leq j < N$.

Define the binary predicate $\text{Pred}$ as a function on the space of the state $s$.

Property 1: For all $j \in [0, N)$, There exists one and only one $i_{m} \in [0, j)$, such that:

$\forall i \in [0, i_{m})$, $\text{Pred}(i, j) = 0$
$\forall i \in [i_{m}, j)$, $\text{Pred}(i, j) = 1$

Property 2: For all $i \in [0, N)$, There exists one and only one $j_{m} \in [i, N)$, such that:

$\forall j \in [i, j_{m})$, $\text{Pred}(i, j) = 1$
$\forall j \in [j_{m}, N)$, $\text{Pred}(i, j) = 0$

                              j = 13, im = 11
                              i = 6, jm = 13
                              ▲
                              │
                 ┌─┬─┬─┬─┬─┬─┬┴┬─┬─┬─┬─┬─┬─┬─┐
               13│0│0│0│0│0│0│0│0│0│0│0│1│1│1│
                 ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘
j = 11, im = 6 12│0│0│0│0│0│0│1│1│1│1│1│1│1│1
i = 2, jm = 11   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘3
         ◄─────11│0│0│0│0│0│0│1│1│1│1│1│1│1
                 ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘2
               10│0│1│1│1│1│1│1│1│1│1│1│1
                 ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘1
                9│0│1│1│1│1│1│1│1│1│1│1
                 ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘0
                8│0│1│1│1│1│1│1│1│1│9
                 ├─┼─┼─┼─┼─┼─┼─┼─┼─┘
 j = 6, im = 1  7│0│1│1│1│1│1│1│1│8
 i = 0, jm = 6   ├─┼─┼─┼─┼─┼─┼─┼─┘
         ◄───── 6│0│1│1│1│1│1│1│7
                 ├─┼─┼─┼─┼─┼─┼─┘
                5│1│1│1│1│1│1│6
                 ├─┼─┼─┼─┼─┼─┘
                4│1│1│1│1│1│5
                 ├─┼─┼─┼─┼─┘
                3│1│1│1│1│4
                 ├─┼─┼─┼─┘
                2│1│1│1│3
                 ├─┼─┼─┘
                1│1│1│2
                 ├─┼─┘
                0│1│1
                 └─┘
                  0

Again, take the figure above as an example. The value of every $\text{Pred}(i, j)$ is shown in the figure at its position $(i, j)$. As a result of Property 1 and Property 2, we could observe the following two situations.

If we fix $i$ and increase $j$, once $\text{Pred}(i, j)$ becomes $0$, it will remain $0$ as we continue increasing $j$.
Similarly, If we fix $j$ and increase $i$, once $\text{Pred}(i, j)$ becomes $1$, it will remain $1$ as we continue increasing $i$.

Now consider the following two problems with this new $\text{Pred}$ :

PROBLEM3: Find $\max(j - i)$, such that $0 \leq i < j < N$ and $\text{Pred}(i, j) = 1$

PROBLEM4: Find the number of states $s = (i, j)$, such that $0 \leq i < j < N$ and $\text{Pred}(i, j) = 1$.

PROBLEM3 is similar to PROBLEM1. We could fix $i$ and increase $j$ until $j = j_m$ . At this point, we have $\text{Pred}(i, j_m) = 0$ . However, this time $j_m$ does not maximize $j - i$ because it does not satisfies the constraint $\text{Pred}(i, j_m) = 1$ . It is the previous point $(i, j_m - 1)$ (if exists) that maximize the $j - i$ .

Once we have reached $(i, j_m)$ for some $i$ , we then fix $j = j_m$ and increase $i$ to $(i_m, j)$ to make $\text{Pred}(i_m, j) = 1$ again. We keep doing these two steps until we reach the final state $(N, N)$ .

In PROBLEM3, we have found a way to visit $j_m$ for each $i$ . Using Property 2 we could know that the number of states $s = (i, j)$ that satisfies $\text{Pred}(i, j) = 1$ is the sum of $j_m - i$ for each $i$ .

                              j = 13, im = 11                               j = 13, im = 11
                              i = 6, jm = 13                                i = 6, jm = 13
                              ▲                                             ▲
                              │                                             │
                 ┌─┬─┬─┬─┬─┬─┬┴──────────┬─┬─┐                 ┌─┬─┬─┬─┬─┬─┬┴┬─┬─┬─┬─┬─┬─┬─┐
               13│0│0│0│0│0│0│xxxxxxxxxxx│1│1│               13│0│0│0│0│0│0│0│0│0│0│0│1│1│1│
                 ├─┼─┼─┼─┼─┼─┤x┌─┬─┬─┬─┬─┼─┼─┘                 ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘
j = 11, im = 6 12│0│0│0│0│0│0│x│1│1│1│1│1│1│1 j = 11, im = 6 12│0│0│0│0│0│0│1│1│1│1│1│1│1│1
i = 2, jm = 11   ├─┼─┴─┴─┴─┴─┘x├─┼─┼─┼─┼─┼─┘3 i = 2, jm = 11   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘3
         ◄─────11│0│xxxxxxxxxxx│1│1│1│1│1│1            ◄─────11│0│0│0│0│0│0│1│1│1│1│1│1│1
                 ├─┤x┌─┬─┬─┬─┬─┼─┼─┼─┼─┼─┘2                    ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘2
               10│0│x│1│1│1│1│1│1│1│1│1│1                    10│0│1│1│1│1│1│1│1│1│1│1│1
                 ├─┤x├─┼─┼─┼─┼─┼─┼─┼─┼─┘1                      ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘1
                9│0│x│1│1│1│1│1│1│1│1│1                       9│0│1│1│1│1│1│1│1│1│1│1
                 ├─┤x├─┼─┼─┼─┼─┼─┼─┼─┘0                        ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘0
                8│0│x│1│1│1│1│1│1│1│9                         8│0│1│1│1│1│1│1│1│1│9
                 ├─┤x├─┼─┼─┼─┼─┼─┼─┘                           ├─┼─┼─┼─┼─┼─┼─┼─┼─┘
 j = 6, im = 1  7│0│x│1│1│1│1│1│1│8            j = 6, im = 1  7│0│1│1│1│1│1│1│1│8
 i = 0, jm = 6   ├─┘x├─┼─┼─┼─┼─┼─┘             i = 0, jm = 6   ├─┼─┼─┼─┼─┼─┼─┼─┘
         ◄───── 6│xxx│1│1│1│1│1│7                      ◄───── 6│0│1│1│1│1│1│1│7
                 │x┌─┼─┼─┼─┼─┼─┘                               ├─┼─┼─┼─┼─┼─┼─┘
                5│x│1│1│1│1│1│6                               5│1│1│1│1│1│1│6
                 │x├─┼─┼─┼─┼─┘                                 ├─┼─┼─┼─┼─┼─┘
                4│x│1│1│1│1│5                                 4│1│1│1│1│1│5
                 │x├─┼─┼─┼─┘                                   ├─┼─┼─┼─┼─┘
                3│x│1│1│1│4                                   3│1│1│1│1│4
                 │x├─┼─┼─┘                                     ├─┼─┼─┼─┘
                2│x│1│1│3                                     2│1│1│1│3
                 │x├─┼─┘                                       ├─┼─┼─┘
                1│x│1│2                                       1│1│1│2
                 │x├─┘                                         ├─┼─┘
                0│x│1                                         0│1│1
                 └─┘                                           └─┘
                  0                                             0

Time Complexity

To visit $j_m$ for each $i$ , both Max Window and Min Window requires you start at the initial state $(0, 0)$ .
The initial state transits to some other state and finally reaches the final state $(N, N)$ .
In PROBLEM1 - 4, we could find that the state never moves back. That is, once the state has reach some $(i, j)$ , it will never moves to some $(m, n)$ such that $m < i$ , $n < j$ .
Furthermore, in PROBLEM1 - 4 we could observe that the state transition is stepwise, i.e. state $(i, j)$ could only transit to its adjacent state $(i + 1, j)$ or $(i, j + 1)$ .
Assume that the cost for one transition is $O(1)$ .
Because the state never moves back, the transition of the state happens at most $O(N)$ times.
Assume the cost of the binary predicate for each state is $O(P)$ .
The time complexity for the sliding window is $O(NP)$ .

Why the name

This algorithm is always referred to as “Sliding Window.” The state $(i, j)$ is defined on the subarray $S[i, j)$ of a given array $S$ in problems. Because the $\text{Pred}$ function is a function of all elements in the subarray $S[i, j)$ , the subarray $S[i, j)$ is called “window”. We increase $j$ to expand the window, then $i$ to shrink the window. This makes the “window” $S[i, j)$ “slide” over $S$ from left to right.

The Duality of Max Window and Min Window

You probably notice that the example of the Min Window is just a flip of the example of the Max Window. Furthermore, the path of the state $(i, j)$ in the Min Window is the same as the path in the Max Window.

                               j = 13, im = 11                                      j = 13, im = 11
                               i = 6, jm = 13                                       i = 6, jm = 13
                               ▲                                                    ▲
                               │                                                    │
                  ┌─┬─┬─┬─┬─┬─┬┴┬─┬─┬─┬─┬─┬─┬─┐                        ┌─┬─┬─┬─┬─┬─┬┴┬─┬─┬─┬─┬─┬─┬─┐
                13│1│1│1│1│1│1│1│1│1│1│1│0│0│0│                      13│0│0│0│0│0│0│0│0│0│0│0│1│1│1│
                  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘                        ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘
 j = 11, im = 6 12│1│1│1│1│1│1│0│0│0│0│0│0│0│1        j = 11, im = 6 12│0│0│0│0│0│0│1│1│1│1│1│1│1│1
 i = 2, jm = 11   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘3        i = 2, jm = 11   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘3
          ◄─────11│1│1│1│1│1│1│0│0│0│0│0│0│1                   ◄─────11│0│0│0│0│0│0│1│1│1│1│1│1│1
                  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘2                           ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘2
                10│1│0│0│0│0│0│0│0│0│0│0│1                           10│0│1│1│1│1│1│1│1│1│1│1│1
                  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘1                             ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘1
                 9│1│0│0│0│0│0│0│0│0│0│1                              9│0│1│1│1│1│1│1│1│1│1│1
                  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘0                               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘0
                 8│1│0│0│0│0│0│0│0│0│9                                8│0│1│1│1│1│1│1│1│1│9
                  ├─┼─┼─┼─┼─┼─┼─┼─┼─┘                                  ├─┼─┼─┼─┼─┼─┼─┼─┼─┘
  j = 6, im = 1  7│1│0│0│0│0│0│0│0│8                   j = 6, im = 1  7│0│1│1│1│1│1│1│1│8
  i = 0, jm = 6   ├─┼─┼─┼─┼─┼─┼─┼─┘                    i = 0, jm = 6   ├─┼─┼─┼─┼─┼─┼─┼─┘
          ◄───── 6│1│0│0│0│0│0│0│7                             ◄───── 6│0│1│1│1│1│1│1│7
                  ├─┼─┼─┼─┼─┼─┼─┘                                      ├─┼─┼─┼─┼─┼─┼─┘
                 5│0│0│0│0│0│0│6                                      5│1│1│1│1│1│1│6
                  ├─┼─┼─┼─┼─┼─┘                                        ├─┼─┼─┼─┼─┼─┘
                 4│0│0│0│0│0│5                                        4│1│1│1│1│1│5
                  ├─┼─┼─┼─┼─┘                                          ├─┼─┼─┼─┼─┘
                 3│0│0│0│0│4                                          3│1│1│1│1│4
                  ├─┼─┼─┼─┘                                            ├─┼─┼─┼─┘
                 2│0│0│0│3                                            2│1│1│1│3
                  ├─┼─┼─┘                                              ├─┼─┼─┘
                 1│0│0│2                                              1│1│1│2
                  ├─┼─┘                                                ├─┼─┘
                 0│0│1                                                0│1│1
                  └─┘         j = 13, im = 11                          └─┘          j = 13, im = 11
                   0          i = 6, jm = 13                            0           i = 6, jm = 13
                              ▲                                                     ▲
                              │                                                     │
                 ┌─┬─┬─┬─┬─┬─┬┴──────────┬─┬─┐                         ┌─┬─┬─┬─┬─┬─┬┴──────────┬─┬─┐
               13│1│1│1│1│1│1│xxxxxxxxxxx│0│0│                       13│0│0│0│0│0│0│xxxxxxxxxxx│1│1│
                 ├─┼─┼─┼─┼─┼─┤x┌─┬─┬─┬─┬─┼─┼─┘                         ├─┼─┼─┼─┼─┼─┤x┌─┬─┬─┬─┬─┼─┼─┘
j = 11, im = 6 12│1│1│1│1│1│1│x│0│0│0│0│0│0│1         j = 11, im = 6 12│0│0│0│0│0│0│x│1│1│1│1│1│1│1
i = 2, jm = 11   ├─┼─┴─┴─┴─┴─┘x├─┼─┼─┼─┼─┼─┘3         i = 2, jm = 11   ├─┼─┴─┴─┴─┴─┘x├─┼─┼─┼─┼─┼─┘3
         ◄─────11│1│xxxxxxxxxxx│0│0│0│0│0│1                    ◄─────11│0│xxxxxxxxxxx│1│1│1│1│1│1
                 ├─┤x┌─┬─┬─┬─┬─┼─┼─┼─┼─┼─┘2                            ├─┤x┌─┬─┬─┬─┬─┼─┼─┼─┼─┼─┘2
               10│1│x│0│0│0│0│0│0│0│0│0│1                            10│0│x│1│1│1│1│1│1│1│1│1│1
                 ├─┤x├─┼─┼─┼─┼─┼─┼─┼─┼─┘1                              ├─┤x├─┼─┼─┼─┼─┼─┼─┼─┼─┘1
                9│1│x│0│0│0│0│0│0│0│0│1                               9│0│x│1│1│1│1│1│1│1│1│1
                 ├─┤x├─┼─┼─┼─┼─┼─┼─┼─┘0                                ├─┤x├─┼─┼─┼─┼─┼─┼─┼─┘0
                8│1│x│0│0│0│0│0│0│0│9                                 8│0│x│1│1│1│1│1│1│1│9
                 ├─┤x├─┼─┼─┼─┼─┼─┼─┘                                   ├─┤x├─┼─┼─┼─┼─┼─┼─┘
 j = 6, im = 1  7│1│x│0│0│0│0│0│0│8                    j = 6, im = 1  7│0│x│1│1│1│1│1│1│8
 i = 0, jm = 6   ├─┘x├─┼─┼─┼─┼─┼─┘                     i = 0, jm = 6   ├─┘x├─┼─┼─┼─┼─┼─┘
         ◄───── 6│xxx│0│0│0│0│0│7                              ◄───── 6│xxx│1│1│1│1│1│7
                 │x┌─┼─┼─┼─┼─┼─┘                                       │x┌─┼─┼─┼─┼─┼─┘
                5│x│0│0│0│0│0│6                                       5│x│1│1│1│1│1│6
                 │x├─┼─┼─┼─┼─┘                                         │x├─┼─┼─┼─┼─┘
                4│x│0│0│0│0│5                                         4│x│1│1│1│1│5
                 │x├─┼─┼─┼─┘                                           │x├─┼─┼─┼─┘
                3│x│0│0│0│4                                           3│x│1│1│1│4
                 │x├─┼─┼─┘                                             │x├─┼─┼─┘
                2│x│0│0│3                                             2│x│1│1│3
                 │x├─┼─┘                                               │x├─┼─┘
                1│x│0│2                                               1│x│1│2
                 │x├─┘                                                 │x├─┘
                0│x│1                                                 0│x│1
                 └─┘                                                   └─┘
                  0                                                     0

This indicates that Max Window problems could be transformed into Min Window problems by just simply negating the $\text{Pred}(i, j)$ function.

After negating the $\text{Pred}(i, j)$ function, we could have PROBLEM3 and PROBLEM4 tranformed into:

PROBLEM3N: Find $\max(j - i)$, such that $0 \leq i < j < N$ and $\text{Pred}(i, j) = 0$
PROBLEM4N: Find the number of states $s = (i, j)$, such that $0 \leq i < j < N$ and $\text{Pred}(i, j) = 0$.

To solve PROBLEM3N, consider how we solve PROBLEM1. For each $i$ , we find its corresponding $j_m$ , the minimum $j$ for this fixed $i$ such that $\text{Pred}(i, j_m) = 1$ . Obviously, for a fixed $i$ , if its corresponding $j_m$ has $j_m > i$ , then we must have $j_{n} = j_m - 1$ , such that $j_n$ is the maximum $j$ that has $\text{Pred}(i, j_n) = 0$ . Then for each $i$ , we could derive $j_n$ from each $j_m$ if $j_m > i$ . $\max(j - i)$ is the maximum among all $j_n$ .

PROBLEM4N is much easier. The number of $(i, j)$ such that $\text{Pred}(i, j) = 0$ is just the number of all states minus the number of the states that have $\text{Pred}(i, j) = 1$ , which is solved in PROBLEM2.

Code Template

Min Window

void SlidingWindow(const std::vector<int>& input) {
  auto i = 0;
  auto j = 0;
  auto ss = SlidingWindowState{};
  auto minWindow = INT_MAX;
  auto numberOfPred1 = 0;
  while(j < input.size()) {
    s.Add(input[j]);
    ++j;
    while(i < j && ss.Pred()) {
      minWindow = std::min(j - i, minWindow);
      numberOfPred1 += input.size() - j + 1;
      s.Remove(input[i]);
      ++i;
    }
  }
}

Max Window

void SlidingWindow(const std::vector<int>& input) {
  auto i = 0;
  auto j = 0;
  auto ss = SlidingWindowState{};
  auto maxWindow = 0;
  auto numberOfPred1 = 0;
  while(i < input.size()) {
    while(j < input.size() && ss.Pred()) {
      maxWindow = std::max(j - i, maxWindow);
      ss.Add(input[j]);
      ++j;
    }
    // j == input.size() || !ss.Pred()
    numberOfPred1 += j - i;
    ss.Remove(input[i]);
    ++i;
  }
}

Combined

Thanks to the duality of Min Window and Max Window, we could use one code template to solve all sliding window problems.

void SlidingWindow(const std::vector<int>& input) {
  auto i = 0;
  auto j = 0;
  auto ss = SlidingWindowState{};
  // PROBLEM1
  auto minWindow = INT_MAX;
  // PROBLEM3N
  auto maxWindow = 0;
  // PROBLEM 2
  auto numberOfPred1 = 0;
  auto numberOfPred0 = 0;
  const auto totalNumberOfNoneEmptySubarray = input.size();
  while(j < input.size()) {
    ss.Add(input[j]);
    ++j;
    while(i < j && ss.Pred()) {
      // ss.Pred() == true, thus we have Pred(i, j) == 1
      // we increase i and find the jm for this i
      // This corresponds to the horizontal part of the 
      // path in the figure.
      // minWindow for each j lies at the right end of each 
      // horizontal part of the path
      minWindow = std::min(j - i, minWindow);
      numberOfPred1 += input.size() - j + 1;
      ss.Remove(i);
      ++i;
    }

    // ss.Pred() == false, thus we have Pred(i, j) == 0
    // This corresponds to the vertical part of the
    // path in the figure
    // maxWindow for each i lies at the top end of each 
    // vertical part of the path
    maxWindow = std::max(j - i, maxWindow);

    numberOfPred0 = totalNumberOfNoneEmptySubarray - numberOfPred1;
  }
}

Selected Problems

MinMax Window

This category of sliding window problems asks you to find the max length subarray or the min length subarray under some conditions.

Leetcode 76 Minimum Window Substring

Given two strings s and t, return the minimum length substring m of s such that m contains every character in t. s and t are not empty. It is guaranteed that there exists a substring of s that contains every character in t.

Define the predicate function Pred(i, j), which returns whether the substring s[i, j) contains every character in t.

Consider the substring ss = s[i, j) of s. s[i, j) starts at index i and ends at index j - 1.

If j == i, then the substring ss is an empty substring. An empty string cannot contain any character in t.
When j increases, new characters will be appended to the substring. As new characters are appended, There will be some j = jm such that s[i, jm) is the first subarray that contains every character in t. (This is guaranteed in the description of the problem.)
For example, take s = "ADOBECODEBANC" t = "ABC".
- When i = 0, we increase j.
- S[i,j) changes as: "", "A", "AD", "ADO", "ADOB", "ADOBE", "ADOBEC".
- "ADOBEC" is the first subarray that contains every character in t.

If the substring s[i, jm) has already contained every character in t, it will remain to contain every character in t no matter how many characters are appended. Thus, Property 2 holds.
If we increase i for some fixed j, as the number of characters in the substring s[i, j) decreases, there will be an im such that the substring s[im, j) does not contain every character in t. Thus, Property 1 holds.
For example, take s = "ADOBECODEBANC" t = "ABC".
- When i = 0, j = 6, we increase i.
- S[i,j) changes as: "ADOBEC", "DOBEC".
- "DOBEC" is the first subarray that does not contain every character in t when j = 6.

Let us consider the time complexity of this algorithm. As mentioned before, the time complexity of the sliding window algorithm is O(NP) where N is the range of i and j, O(P) is the time complexity of calling Pred.

To check whether a string a contains all characters in b, we could count the frequency of letters in a and b and compare their frequency. Counting the frequency of substring s[i, j) could be at worst O(N) time, where N is the length of the string s. Thus calling Pred needs O(N) time. The time complexity of this sliding window algorithm will be O(N * N) = O(N^2), which is not acceptable given the constraint N ~ 10^5.

To optimize the time complexity of Pred, we consider the following approaches:

Maintain the letter frequency of the subarray online. This is achieved by updating the frequency when i or j changes. When j increases to j + 1, add 1 to the frequency of the letter s[j]. When i increases to i + 1, decrease 1 from the frequency of the letter s[i].
Compute the letter frequency of the string t, FreqTin advance.
Pred is then implemented to compare the frequency of 52 letters ([a - z][A - Z]) of FreqS and FreqT. In this way, the time complexity of Pred is O(52) = O(1).
The overall time complexity of the sliding window algorithm becomes O(N), which is acceptable for N ~ 10^5.

The following figure shows the path of (i, j) in the sliding window algorithm. s = "ADOBECODEBANC", t = "ABC"

    t = A B C          │minLength = 4
        1 1 1          │subarray = "BANC"
  ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐▼┌─┬─┬─┬─┐
13│$│ │ │ │ │ │ │1│1│1│1│0│ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
12│C│ │ │ │ │ │ │0│ │ │ │ │ │0│$│
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘
11│N│ │1│1│1│1│1│0│ │ │ │ │0│C│1
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘3
10│A│ │0│ │ │ │ │ │ │ │ │0│N│1
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘2
 9│B│ │0│ │ │ │ │ │ │ │0│A│1
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘1
 8│E│ │0│ │ │ │ │ │ │0│B│1
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘0
 7│D│ │0│ │ │ │ │ │0│E│9
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┘
 6│O│1│0│ │ │ │ │0│D│8
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┘
 5│C│0│ │ │ │ │0│O│7
  ├─┼─┼─┼─┼─┼─┼─┼─┘
 4│D│0│ │ │ │0│C│6
  ├─┼─┼─┼─┼─┼─┼─┘
 3│B│0│ │ │0│E│5
  ├─┼─┼─┼─┼─┼─┘
 2│O│0│ │0│B│4
  ├─┼─┼─┼─┼─┘
 1│D│0│0│O│3
  ├─┼─┼─┼─┘
 0│A│0│D│2
  └─┼─┼─┘
    │A│1
    └─┘
     0

In the following code:

Function MakeFreq computes the letter frequency of t in advance.
curFreq is the letter frequency that we maintain online.
Function CheckFreq could be seen as the Pred function mentioned above.

[Leetcode 76 Minimum Window Substring]

using Freq = std::array<int, 52>;

int CharToIdx(char c) {
  if(c >= 'a' && c <= 'z') {
    return c - 'a';
  } else {
    // c in [A - Z]
    return c - 'A' + 26;
  }
}

Freq MakeFreq(const std::string& t) {
  auto res = Freq{};
  for(const char c : t) {
    ++res[CharToIdx(c)];
  }
  return res;
}

bool CheckFreq(const Freq& t, const Freq& p) {
  for(int i = 0; i < t.size(); ++i) {
    if(p[i] == 0) {
      continue;
    }
    // p[i] != 0
    if(t[i] < p[i]) {
      return false;
    }
  }
  
  return true;
}

class Solution {
public:
    string minWindow(const std::string& s, const std::string& t) {
      const auto pFreq = MakeFreq(t);
      auto curFreq = Freq{};
      
      auto first = 0;
      auto last = 0;
      auto res = std::optional<std::string_view>{};
      while(last < s.size()) {
        const auto curIdx = CharToIdx(s[last++]);
        ++curFreq[curIdx];
        while(CheckFreq(curFreq, pFreq)) {
          if(!res || last - first < res->size()) {
            res = std::string_view(s.data() + first, last - first);
          }
          const auto removeIdx = CharToIdx(s[first++]);
          --curFreq[removeIdx];
        }
      }
      return std::string{*res};
    }
};

Leetcode 632 Smallest Range Covering Elements from K Lists

Leetcode 632. Smallest Range Covering Elements from K Lists

You have k lists of sorted integers in non-decreasing order. Find the smallest range that includes at least one number from each of the k lists.
Example:
Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output: [20, 24]

Such smallest range (inclusive) must start and end with the numbers from the k lists. This can be proved by contradiction. Assume range r = [a, b] is the smallest range such that it includes at least one number from each of the k lists. Assume that a is not a number from the k lists, then there exists a number a1, such that a1 is a number from the k lists and a1 > a. Then there exists another range r1 = [a1, b] which is smaller than range r = [a, b]. Again, if we assume that b is not a number from the k lists, we could also find another smaller range r2 = [a, b2]. Thus we have a and b are both numbers from the k lists.

The problem becomes Finding two numbers i and j from the numbers in k lists such that:

i < j
each of the k lists has a number included in the range [i, j]
[i, j] is the smallest such range.

We associate every number with its list’s index. Then merge the number index pairs altogether. For example, the input

1	input = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]

becomes

1
2
3

nks = [(0, 1), (4, 0), (5, 2), (9, 1), (10, 0), (12, 1),
 (15, 0), (18, 2), (20, 1), (22, 2), (24, 0), 
 (26, 0), (30, 2)]

The problem is transformed into Finding two index i, j of the array nks, such that:

i < j
nks[i, j] includes elements from every lists.
the range represented by the number nks[i] and the number nks[j] is the smallest.

We could notice that this is a minimum sliding window problem.

The empty range cannot include elements from every list.
If i is fixed, as j increases, there will be some jm such that [i, jm] includes elements from every list. Besides, if we continue increasing j after reaching jm, no matter what we append after the range [i, jm], it will always include elements from every list. (PROPERTY1)
If j is fixed, as i increases, there will be some im such that [im, j] does not include elements from every list. Besides, if we continue increasing i after reaching im, it will never include elements from every list again. (PROPERTY2)

To solve the problem with a minimum sliding window, we need to design the Pred function. In this problem, Pred(i, j) checks whether the range nks[i, j] contains elements from all k lists.

This could be done trivially by traversing all the elements in the range nks[i, j] and computing the frequency of each list. If the frequency of each list is greater than or equal to one, then Pred(i, j) = 1, otherwise 0. This trivial method has a time complexity O(N + K), where N is the number of elements in nks and K is the number of lists. The minimum sliding window algorithm has an overall complexity O(N(N+K)) ~ O(N^2 + NK). Given the constraint k ~ 3500 and N ~ 50 * 3500 = 175000, O(N^2 + NK) is not acceptable when N ~ 2 * 10^5. We have to come up with an optimized Pred with time complexity not greater than logarithm.

Consider the statement “at least one number from each of the k lists.” This statement is equivalent to “the minimum frequency of numbers from each of the k lists is greater than or equal to 1.”

This equivalence indicates that to design Pred, we have to design a data structure that supports the following operations online:

A is an array.
initialize all elements in A as 0.
increase A[k] by 1.
decrease A[k] by 1.
return the minimum element in A.

Let us call this data structure FreqCounter. FreqCounter could be implemented by combining an array with a priority queue. The priority queue contains elements with outdated frequency. Before each query, outdated elements at the top of the priority queue will be discarded. A detailed discussion of this data structure is beyond the scope of this blog post.

Implementation of FreqCounter

struct FreqCounter{
  
  struct FreqK{
    int freq_;
    int k_;
  
    friend bool operator<(FreqK lhs, FreqK rhs) {
      return lhs.freq_ > rhs.freq_;
    }
  };
  
  explicit FreqCounter(int cap)
  :freqs_(cap, 0)
  {
    for(int i = 0; i < cap; ++i) {
      pq_.push(FreqK{0, i});
    }
  }
  
  void Add(int k) {
    ++freqs_[k];
    pq_.push(FreqK{freqs_[k], k});
  }
  
  void Remove(int k) {
    --freqs_[k];
    pq_.push(FreqK{freqs_[k], k});
  }
  
  int QueryMin() {
    while(pq_.top().freq_ != freqs_[pq_.top().k_]) {
      pq_.pop();
    }
    
    return pq_.top().freq_;
  }
  
  std::vector<int> freqs_;
  std::priority_queue<FreqK> pq_{};
};

With the help of FreqCounter, Pred could be done in logarithm time. The minimum sliding window algorithm is implemented as follows:

Before increasing j, we call FreqCounter::Add to add one to the list where nks[j] belongs. (Line 44)
Pred is implemented by checking FreqCounter::QueryMin > 0. If the result of FreqCounter::QueryMin is greater than 0, then the range [i, j) includes elements from every list. (Line 45)
Before increasing i, we call FreqCounter::Remove to decrease one to the list where nks[i] belongs. (Line 51)

[Leetcode 632 Smallest Range Covering Elements from K Lists]

struct NumK{
  int num_;
  int k_;
  
  friend bool operator<(NumK lhs, NumK rhs) {
    return lhs.num_ < rhs.num_;
  }
};

struct Res{
  int a_;
  int b_;
  
  int Size() const {
    return b_ - a_;
  }
  
  friend bool operator<(Res lhs, Res rhs) {
    return lhs.Size() == rhs.Size() ?
           lhs.a_ < rhs.a_ :
           lhs.Size() < rhs.Size();
  }
};

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
      auto nks = std::vector<NumK>{};
      for(int k = 0; k < nums.size(); ++k) {
        for(const auto n : nums[k]) {
          nks.push_back(NumK{n, k});
        }
      }
      std::sort(nks.begin(), nks.end());
            
      auto freqCounter = FreqCounter(nums.size());
      auto first = 0;
      auto last = 0;
      
      auto res = std::optional<Res>{};

      while(last < nks.size()) {
        const auto nk = nks[last++];
        freqCounter.Add(nk.k_);
        while(first < last && freqCounter.QueryMin() > 0) {
          const auto curRes  = Res{nks[first].num_, nks[last - 1].num_};
          if(!res || curRes < *res) {
            res = curRes;
          }
          const auto removeK = nks[first++].k_;
          freqCounter.Remove(removeK);
        }
      }
      
      return std::vector<int>{res->a_, res->b_};
    }
};

Leetcode 424 Longest Repeating Character Replacement

Given a string s with only uppercase English letters and an integer k. You can change any character in s to any other uppercase English letter. You can do this operation at most k times. Return the maximum length of the single letter subarray of s after you perform the above operation.

Consider the substring s[i, j). The minimum number of operations that you need to make s[i, j) a single letter substring is j - i - MaxFreq(i, j), where MaxFreq(i, j) returns the maximum frequency of the letters in the substring s[i, j).

For example, consider the substring ss = "AABA". MaxFreq is 3, which is the frequency of A because it is the largest frequency in the substring. Then the number of operations is 4 - 3 = 1, which means we have to change all other characters with lower frequency than A into A.

Now consider the changing of j - i - MaxFreq(i, j) when we increase j or i.

When we fix i and increase j, j - MaxFreq(i, j) is a non-decreasing function. The monotonicity is because when we add a new character in the substring s[i, j) by increasing j:
- MaxFreq(i, j) could increase 1.
- MaxFreq(i, j) may not change.
- j always increases 1.
When we fixe j and increase i, -i - MaxFreq(i, j) is a non-increasing function, which is due to a similar reason as above.

Therefore, if we define Pred(i, j) = (j - i - MaxFreq(i, j)) > k, this problem becomes a minimum sliding window. We need to get the longest subarray such that Pred(i, j) = 0, which is just PROBLEM3N.

The MaxFreq(i, j) could be maintained by combining a priority queue with an array, which is similar to the FreqCounter in the previous problem Leetcode 632 Smallest Range Covering Elements from K Lists.

[Leetcode 424 Longest Repeating Character Replacement]

struct MaxFreq{
  
  struct CharFreq{
    char c_;
    int freq_;
    
    friend bool operator<(CharFreq l, CharFreq r) {
      return l.freq_ < r.freq_;
    }
  };
  
  int Max() {
    assert(!pq_.empty());
    while(pq_.top().freq_ != GetFreq(pq_.top().c_)) {
      pq_.pop();
    }
    
    return pq_.top().freq_;
  }
  
  void Add(char c) {
    ++GetFreq(c);
    pq_.push(CharFreq{c, GetFreq(c)});
  }
  
  void Remove(char c) {
    --GetFreq(c);
  }
  
  int& GetFreq(char c) {
    return freq_[c - 'A'];
  }
  
  std::array<int, 26> freq_{};
  std::priority_queue<CharFreq> pq_{};
};

class Solution {
public:
    int characterReplacement(const std::string& s, int k) {
      auto i = 0;
      auto j = 0;
      auto mf = MaxFreq{};
      auto res = 0;
      while(j < s.size()) {
        mf.Add(s[j++]);
        while(j - i - mf.Max() > k) {
          mf.Remove(s[i++]);
        }
        
        // j - i - mf.Max() <= k
        res = std::max(res, j - i);
      }
      return res;
    }
};

Leetcode 1156 Swap For Longest Repeated Character Substring

Given a string s, you can swap two characters in s. Return the length of the longest single letter substring.

This problem is similar to Leetcode 424 Longest Repeating Character Replacement. In Leetcode 424, you can replace any character with any other character. However, in this problem, you could only replace one character with another character in s.

As mentioned in the previous problem, the number of characters that we need to swap in the current substring is j - i - MaxFreq(i, j).

Given that we could only swap two characters(swap once), we have to define the predicate as Pred = j - i - MaxFreq(i, j) > 1. (Line 59)
When Pred = 0, we then check if there are enough characters we could swap into the substring. (Lines 63 - 68)
- We first find which character has the maximum frequency in the substring. (Line 63)
- Then, all other characters in the substring will be replaced with the maximum frequency character. (Line 64)
- If we could do this swap, we must have “total number of maximum frequency character in s“ - “number of maximum frequency character in the substring” >= “number of other characters in the substring” (Line 65 - 66).

[Leetcode 1156 Swap For Longest Repeated Character Substring]

using Freq = std::array<int, 26>;

struct MaxFreq{
  
  struct CharFreq{
    char c_;
    int freq_;
    
    friend bool operator<(CharFreq l, CharFreq r) {
      return l.freq_ < r.freq_;
    }
  };
  
  std::pair<char, int> Max() {
    assert(!pq_.empty());
    while(pq_.top().freq_ != GetFreq(pq_.top().c_)) {
      pq_.pop();
    }
    
    return std::make_pair(pq_.top().c_, pq_.top().freq_);
  }
  
  void Add(char c) {
    ++GetFreq(c);
    pq_.push(CharFreq{c, GetFreq(c)});
  }
  
  void Remove(char c) {
    --GetFreq(c);
  }
  
  int& GetFreq(char c) {
    return freq_[c - 'a'];
  }
  
  Freq freq_{};
  std::priority_queue<CharFreq> pq_{};
};

Freq MakeFreq(const std::string& s) {
  auto res = Freq{};
  for(auto c : s) {
    ++res[c - 'a'];
  }
  return res;
}

class Solution {
public:
    int maxRepOpt1(const std::string& s) {
      auto i = 0;
      auto j = 0;
      auto mf = MaxFreq{};
      auto freq = MakeFreq(s);
      auto res = 0;
    
      while(j < s.size()) {
        mf.Add(s[j++]);
        while(j - i - mf.Max().second > 1) {
          mf.Remove(s[i++]);
        }
        
        const auto [replaceChar, maxFreq] = mf.Max();
        const auto numberOfCharsToSwap = j - i - maxFreq;
        const auto numberOfRemaining = freq[replaceChar - 'a'] - maxFreq;
        if(numberOfRemaining >= numberOfCharsToSwap) {
          res = std::max(res, j - i);
        }
      }
      
      return res;
    }
};

Leetcode 727 Minimum Window Subsequence

Given strings s1 and s2, return the minimum contiguous substring part of s1 so that s2 is a subsequence of the part.

We could easily observe that the substring ss1 = s1[i, j) of s1 and the predicate Pred = “s2 is a subsequence of ss1.” together form a minimum sliding window.

If we fix i and increase j, there will be some j = jm, such that s2 is a subsequence of s1[i, jm). If we continue increasing j after we have reached jm, the substring s1[i, j), j > jm still has s2 as its subsequence.

For example, s1 = "abcdebdde", s2 = "bde". If we fix i = 0 and increase j, we could have jm = 5. The substring s1[i, jm) is "abcde". If we continue increasing j at this point, no matter how many letters we append after the window, s2 = "bde" is still a subsequence of s1[i, j).
If we fix j and increase i, there will be some i = im, such that s2 is not a subsequence of s1[im, j). If we continue increasing i after we have reached im, the substring s1[i, j), i > im cannot have s2 as its subsequence again.

For example, s1 = "abcdebdde", s2 = "bde". If we fix j = 5 and increase i, we could have im = 2. The substring s1[im, j) is "cde". If we continue increasing i at this point, no matter how many letters we discard at the front of the window, s2 = "bde" is still not a subsequence of s1[i, j).

Then we have to design the predicate Pred = “s2 is a subsequence of ss1.” A trivial design of the predicate is to have one pointer at the start of ss1 and another pointer at the start of s2. The idea is shown in the code below.

Trivial IsSubsequence

bool IsSubsequence(std::string_view s1, std::string_view s2) {
  auto* first1 = s1.data();
  auto* last1 = s1.data() + s1.size();
  
  auto* first2 = s2.data();
  auto* last2 = s2.data() + s2.size();
  
  while(first1 < last1 && first2 < last2) {
    if(*first1 == *first2) {
      ++first1;
      ++first2;
    } else {
      ++first1;
    }
  }
  
  // first1 == last1 || first2 == last2
  if(first2 == last2) {
    return true;
  }
  
  return false;
}

However, this implementation has a time complexity of O(max(S1, S2)) = S1, where S1 is the length of the string s1 and S2 the length of the string s2(If s2 is a subsequence of s1, we must have S2 <= S1). The overall complexity of the minimum sliding window will be O(S1^2). Given the constraint S1 ~ 2 * 10^4, this is not acceptable. Again, to optimize the time complexity, we have to maintain the predicate online.

While the window is expanding(i.e., while j is increasing), maintaining the predicate is easy. We keep the pointer matchIdx_ pointing to the next unmatched character of the pattern string s2. If we read in a new character (i.e., when j is increasing), we compare it against s2[matchIdx_]. If they are the same character, we increase matchIdx_. If matchIdx_ == s2.size(), we know that the current substring s1[i, j) has s2 as its subsequence.

However, it can be hard to maintain the predicate while the window is shrinking (i.e., while i is increasing). The solution is: we do not shrink the window step by step. Instead, when j is fixed, we could jump to im directly!

Consider the substring s1[i, jm). s1[jm - 1] must be the last character of s2. We can prove it by contradiction. Given the substring s1[i0, jm), where j = jm is the smallest j for i0, such that s2 is a subsequence of s1[i0, jm). Assume that s1[jm - 1] != s2[S2 - 1]. Because s2 is a subsequence of s1[i0, jm) and s1[jm - 1] != s2[S2 - 1], there must be some j0 < jm - 1 such that s1[j0] == s2[S2 - 1]. Then we could have another substring s1[i0, j0 + 1) for this i0, that has s2 as its subsequence. This substring s1[i0, j0 + 1) has its ending j0 + 1 < jm, which contradicts the assumption that jm is the smallest such j. Thus, we proved that s2[jm - 1] must be the last character of s2 by contradiction.

For example, if we have s1[i, jm) = "abcde", s2 = "bde". Then we could start with the last character 'e' of s1[i, jm) and match backward. sss1 = bcde" in this case.
This idea is shown in the following code.

Given that s1[jm - 1] must be the last character of s2, we could match s2 against s1 backward to find the smallest substring sss1 ending at jm of the substring s1[i, jm).

Find Smallest Substring BackWards

int FindSmallestSubstringReversely(std::string_view ss1, std::string_view s2) {
  auto match = s2.size();
  auto pIdx = s2.size() - 1;
  auto sIdx = ss1.size() - 1;
  while(match > 0) {
    if(ss1[sIdx] == s2[pIdx]) {
      --pIdx;
      --match;
    }
    --sIdx;
  }`
  return sIdx + 1;
}

Then the im for this j is simply the index of second character n of sss1 in s1. Because this i = im must be the first i for this fixed j such that s1[im, j) starts not taking s2 as its subsequence.

Notice that after we move i to im, we have to recompute the matchIdx_. We have to recompute how many characters are matched in the substring s1[im, j).

For example, if we have s1 = "abcdebdde", s1[0, 5) = "abcde", s2 = "bde". Then sss1 = "bcde", we move im to the second character 'c' in sss1, which has index = 2 in s1.

Then the minimum sliding window algorithm goes as follows:

Before increasing j, we match s1[j] against s2[matchIdx_] to update the predicate ss. (Line 73)
If the current window has s1 as its subsequence, we jump directly to the im of this j. (Line 75)

[Leetcode 727 Minimum Window Subsequence]

struct Subsequence{
  
  void Add(char c) {
    if(c == p_[matchIdx_]) {
      ++matchIdx_;
    }
    
    s_.push_back(c);
  }
  
  bool IsSubsequence() const {
    return matchIdx_ == p_.size();
  }
  
  int NextMatch() {
    assert(IsSubsequence());
    assert(s_.back() == p_.back());
    // Find the minimum substring of s_ that p_ is the subsequence of.
    const auto rmSeqFirst = FindSmallestSubstringReversely() + 1;
    const auto numberOfCharsPoppedFront = rmSeqFirst;
    const auto newS = s_.substr(rmSeqFirst);
    matchIdx_ = 0;
    s_.clear();
    for(auto c : newS) {
      Add(c);
    }
    return numberOfCharsPoppedFront;
  }
  
  int FindSmallestSubstringReversely() {
    auto match = p_.size();
    auto pIdx = p_.size() - 1;
    auto sIdx = s_.size() - 1;
    while(match > 0) {
      if(s_[sIdx] == p_[pIdx]) {
        --pIdx;
        --match;
      }
      --sIdx;
    }
    return sIdx + 1;
  }
  
  std::string_view p_;
  int matchIdx_{0};
  std::string s_{};
};

struct Res{
  int a_;
  int b_;
  
  int Size() const {
    return b_ - a_;
  }
  
  friend bool operator<(Res lhs, Res rhs) {
    return lhs.Size() == rhs.Size() ?
           lhs.a_ < rhs.a_ :
           lhs.Size() < rhs.Size();
  }
};

class Solution {
public:
    string minWindow(const std::string& s1, const std::string& s2) {
      // Is s2 a subsequence of s1[i, j)?
      auto res = std::optional<Res>{};
      auto ss = Subsequence{s2};
      auto first = 0;
      auto last = 0;
      while(last < s1.size()) {
        ss.Add(s1[last++]);
        if(ss.IsSubsequence()) {
          first += ss.NextMatch(); 
          const auto newRes = Res{first - 1, last};
          if(!res || !(res < newRes)) {
            res = newRes;
          }
        }
      }
      
      return std::string(s1.data() + res->a_, res->b_ - res->a_);
    }
};

Counting Window

Leetcode 713 Subarray Product Less Than K

Given an array nums with all elements greater than 0. Find the number of subarrays such that the product of elements in the subarray is less than k.

Consider the subarray nums[i, j). Because every element in the subarray is greater than 0, we have:

If we fix i and increase j, then the product of elements in the subarray must increase. There will be some j = jm that makes the product of the subarray no longer less than k.
If we fix j and increase i, then the product of elements in the subarray must decrease. There will be some i = im that makes the product of the subarray less than k.

This indicates that the subarray and the product of its elements form a maximum sliding window. Because of the duality of maximum sliding window and minimum sliding window, we negate the original condition and transform it into “the product of elements in the subarray is greater than or equal to k.” We call this condition Pred.

We count the number of subarrays that have Pred(i, j) = 1 as in PROBLEM2. The total number of non-empty subarrays is (n * (n - 1)) / 2, where n is the size of nums. Then the number of subarrays that have Pred(i, j) = 0 could be derived by subtracting the number of Pred(i, j) = 1 out of the total number of non-empty subarrays.

[Leetcode 713 Subarray Product Less Than K]

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
      int64_t prod = 1;
      auto i = 0;
      auto j = 0;
      const int n = nums.size();
      auto num = 0;
      while(j < nums.size()) {
        prod = prod * nums[j++];
        while(i < j && prod >= k) {
          num += n - j + 1;
          prod = prod / nums[i++];
        }
      }
      const auto totalNumberOfSubarrays = ((1 + n) * n) / 2;
      return totalNumberOfSubarrays - num;
    }
};

Leetcode 1248 Count Number of Nice Subarrays

Given an array with positive integers, return the longest subarray such that it contains exactly k odd integers.

Consider the following problem Leetcode 1248 SUBPROBLEM:

Given an array with positive integers, return the longest subarray such that it contains less than k odd integers.

This problem could be solved easily by a maximum sliding window. It is the same problem as PROBLEM3N.

Just maintain a variable numberOfOdds counting the number of odds in the subarray. When numberOfOdds >= k, shrink the window.

[Leetcode 1248 SUBPROBLEM]

int NumberOfSubarraysLessThanK(const std::vector<int>& nums, int k) {
  auto numberOfOdds = 0;
  auto i = 0;
  auto j = 0;
  auto n = 0;
  const auto sz = nums.size();
  const auto totalNumberOfSubarrays = (sz * (sz + 1)) / 2;
  
  while(j < nums.size()) {
    const auto jVal = nums[j++];
    numberOfOdds += (jVal & 1);
    while(numberOfOdds >= k) {
      n += sz - j + 1;
      const auto iVal = nums[i++];
      numberOfOdds -= (iVal & 1);
    }
  }
  
  return totalNumberOfSubarrays - n;
}

After solving Leetcode 1248 SUBPROBLEM, the original problem could be solved by “the number of arrays have less than (k + 1) odds” minus “the number of arrays have less than (k) odds”

[Leetcode 1248 Count Number of Nice Subarrays]

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
      return NumberOfSubarraysLessThanK(nums, k + 1) - NumberOfSubarraysLessThanK(nums, k);
    }
};

Leetcode 1918 Kth Smallest Subarray Sum

Given a positive integer array nums of length n and an integer k, return the kth smallest subarray sum.

Consider the following problem Leetcode 1918 Kth Smallest Subarray Sum SUBPROBLEM:

Given the function NumberOfElementsLessThan(N), which returns the number of elements in the array that is less than or equal to N. The maximum element of the array is max, the minimum element of the array is min, and return the kth smallest element.

Let us take the array [1, 2, 3, 3, 4, 6] as an example.

There are 1 element less than or equal to the 1st smallest element — 1.
There are 2 elements less than or equal to the 2nd smallest element — 2.
There are 4 elements less than or equal to the 3rd smallest element — 3.
There are 4 elements less than or equal to the 4th smallest element — 3. (Notice that there are two 3s in the array.)
There are 5 elements less than or equal to the 5th smallest element — 4.
There are 6 elements less than or equal to the 5th smallest element — 6.

If we want to find the 3rd smallest element, we find the first element such that there are greater or equal 3 elements that are less than or equal to it.

If we want to find the 4th smallest element, we find the first element such that there are greater or equal 4 elements that is less than or equal to it. This will lead us to the first 3 in the array, but it does not matter because the 3rd smallest element and the 4th smallest element are the same.

Because there could be some elements that have the same value, the kth element does not necessarily have k elements less than or equal to it. (For example, the 3rd element 3 in the array has 4 elements less than or equal to it.)

Thus, if we want to find the kth smallest element, we could find the first element such that there are greater or equal k elements that are less than or equal to it.

Notice that the number of elements less than or equal to the kth smallest element is strictly increasing w.r.t k. Therefore, Leetcode 1918 Kth Smallest Subarray Sum SUBPROBLEM could be solved by binary search on the range [min, max + 1). The predicate is designed to be:

1
2
3

int Pred(int n) {
  return NumberOfElementsLessThan(n) < k;
}

Then the binary search will stop at the first element such that NumberOfElementsLessThan(n) >= k. This element is the kth smallest element.

Now let us get back to the original problem. The original problem asks you to find the kth smallest subarray sum. We know that by sliding window, we could compute the number of subarrays such that its sum is less than or equal to a certain number N. By Leetcode 1918 Kth Smallest Subarray Sum SUBPROBLEM, the kth smallest subarray sum in the range [0, S) is the first number such that it has greater than or equal to k subarray sums that are less than or equal to it. S is the largest sum, the sum of all elements in the array. We could use binary search to find the kth element as in Leetcode 1918 Kth Smallest Subarray Sum SUBPROBLEM.

[Leetcode 1918 Kth Smallest Subarray Sum]

int NumberOfSubarraysSumLessThanN(const std::vector<int>& nums, int N) {
  auto i = 0;
  auto j = 0;
  auto sum = 0;
  auto n = 0;
  const auto sz = nums.size();
  const auto total = (sz * (sz + 1)) / 2;
  while(j < sz) {
    sum += nums[j++];
    while(sum > N) {
      n += sz - j + 1;
      sum -= nums[i++];
    }
  }
  return total - n;
}

template<typename Pred>
int BinarySearch(int first, int last, Pred pred) {
  while(first < last) {
    auto mid = first + (last - first) / 2;
    if(pred(mid)) {
      first = mid + 1;
    } else {
      last = mid;
    }
  }
  return first;
}

class Solution {
public:
  int kthSmallestSubarraySum(vector<int>& nums, int k) {
    const auto totalSum = std::accumulate(nums.begin(), nums.end(), 0);
    return BinarySearch(0, totalSum + 1, [&nums, k](int sum){
      return NumberOfSubarraysSumLessThanN(nums, sum) < k;
    }); 
  }
};

Xuanyi Fu Blog

Partition Point : Sliding Window

Introduction

Min Window

Max Window

Time Complexity

Why the name

The Duality of Max Window and Min Window

Code Template

Min Window

Max Window

Combined

Selected Problems

MinMax Window

Leetcode 76 Minimum Window Substring

Leetcode 632 Smallest Range Covering Elements from K Lists

Leetcode 424 Longest Repeating Character Replacement

Leetcode 1156 Swap For Longest Repeated Character Substring

Leetcode 727 Minimum Window Subsequence

Other Problems

Counting Window

Leetcode 713 Subarray Product Less Than K

Leetcode 1248 Count Number of Nice Subarrays

Leetcode 1918 Kth Smallest Subarray Sum

Other Problems