Sliding Window with a Dynamic Size

Let's use Longest Substring Without Repeating Characters as our example.

A brute-force approach would consist in checking every substring and stop as soon as we find a duplicated characters. We have a total of $O(n^2)$ substrings and we would require $O(n)$ to look for duplicated characters. So our total time complexity would be $O(n^3)$, where $n$ is the length of the string.

In this case, we do not have an explicit window of a certain size as for the previous example. However, we can still apply a sliding window algorithm.

In fact, suppose that we do not have repeated characters in the input string: the window will be the entire string itself.

Now, let's suppose to have an example like abcdaefghi. Here, a is the duplicated character, which is at positions 0 and 4. We can build a window from the first a till the second one, then, we can shrink the window till the a is not repeated anymore, which means that the window will start from b to a (1 till 4). Lastly, we can continue increasing our window till the end, since we do not have other duplicated characters.

The implementation would look something like:

from typing import Set


class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        chars: Set[str] = set()
        ans = left = 0

        for right, char in enumerate(s):
            while char in chars:
                chars.remove(s[left])
                left += 1

            chars.add(char)

            win_size = right - left + 1
            ans = max(ans, win_size)

        return ans

Which has the following complexity:

• Time: $O(n)$
• Space: $O(m)$

Where $n$ is the size of the string $s$ and $m$ is the number of distinct characters in the string $s$.