Competitive Programming #1: Sliding Window Technique

An algorithm technique for efficiently solving a problem for arrays and lists. The goal is to iterate through or slide the data structure from one end to another, maintaining the sliding window. Using this technique, you can solve problems such as finding the maximum sum and longest substring, etc., within that window.

Let’s consider an example where an array has a size of six and contains some values. For now, we will check how the sliding window works.

sliding window = 3

Photo By: Author

Sliding window techniques start from index 0 (left) to index 5 (right). Iteration starts from index 0 and stops at index three because the given sliding window is three, and this sliding window needs to be maintained constantly.

That said, we can’t do sliding at index four because (index + sliding window) is more than the array size.

There are two types of sliding windows:

1. Fixed window: The sliding window size is permanently fixed or constant.
2. Variable window: The sliding window size can increase or decrease based on some conditions.

Let’s look at a problem and find a solution:

Problem: Find the maximum sum of k consecutive elements in an array.

'''
Find the maximum sum of k consecutive elements in an array.
'''


def max_sum_subarray(nums, sliding_window):
    # init
    max_sum = -1

    # sliding window from left to right
    for i in range(len(nums) - sliding_window + 1):
        value = sum(nums[i: i + sliding_window])
        if value > max_sum:
            max_sum = value
    return max_sum


arr = [2, 3, 5, 8, 9, 10]
sliding_window = 3
print("maximum sum of k consecutive elements in an array is: ",
      max_sum_subarray(arr, sliding_window))

As described in the above section, the solution to this problem follows the same trend: we iterate from left to right with the sliding window to find the maximum sum of k consecutive elements.

Now, let’s look at an optimized version of the code:

'''
Find the maximum sum of k consecutive elements in an array.
'''


def max_sum_subarray(nums, sliding_window):
    # find the initial sum of the sliding window
    value = sum(nums[:sliding_window])
    max_sum = value

    # sliding window from left to right
    for i in range(1, len(nums) - sliding_window + 1):
        value = value - nums[i-1] + nums[i+sliding_window-1]
        max_sum = max(value, max_sum)
    return max_sum


arr = [2, 3, 5, 8, 9, 10]
sliding_window = 3
print("maximum sum of k consecutive elements in an array is: ",
      max_sum_subarray(arr, sliding_window))

This optimization code only sums once for the sliding window, substructing the element left behind and adding the new element that enters the sliding window. Pretty simple.

Time Complexity: O(n). The complexity is linear since each element is added and subtracted only once.

Further Optimization: In some cases, additional optimizations can be applied by dynamically adjusting the sliding window size or combining the sliding window with other techniques, such as binary search or dynamic programming.

Let’s solve a complicated problem from Leetcode using the sliding window technique:

Problem: https://leetcode.com/problems/substring-with-concatenation-of-all-words/description/

You are given a string s and an array of strings words. All the strings of words are of the same length.

A concatenated string is a string that exactly contains all the strings of any permutation of words concatenated.

For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated string because it is not the concatenation of any permutation of words.
Return an array of the starting indices of all the concatenated substrings in s. You can return the answer in any order.

 

Example 1:

Input: s = "barfoothefoobarman", words = ["foo","bar"]

Output: [0,9]

Explanation:

The substring starting at 0 is "barfoo". It is the concatenation of ["bar","foo"] which is a permutation of words.
The substring starting at 9 is "foobar". It is the concatenation of ["foo","bar"] which is a permutation of words.

One way to solve this is to get the permutations of the list of words, then check if permutation exists in the string “s”; if it does, then get the starting index number and append it to a list.

'''
https://leetcode.com/problems/substring-with-concatenation-of-all-words/description/
'''


def permute_list(words):
    # Base case
    if len(words) == 1:
        return [words]
    # store the permutations of strings inside the list
    permutations = []

    for i in range(len(words)):
        current = words[i]
        remaining = words[:i] + words[i+1:]
        # recursively permute the remaining words
        for j in permute_list(remaining):
            permutations.append([current] + j)
    return permutations


def findSubstring(s, words):
    permutations = permute_list(words)
    # conver the permutations into list of strings
    permutation_strings = [''.join(p) for p in permutations]

    # result strting index
    result = []
    for p in permutation_strings:
        if p in s:
            index = s.find(p)
            result.append(index)

    return result


print(findSubstring("barfoothefoobarman", ["foo", "bar"]))

Time Complexity: O(n×n!+n!×m×k)
Space Complexity: O(n!×(n+k))

This brute-force approach could be more inefficient for significant inputs. Now, set that aside and focus on the sliding window technique. That’s our goal, after all.

'''
https://leetcode.com/problems/substring-with-concatenation-of-all-words/description/
'''
from collections import defaultdict


def findSubstring(s, words):
    # base case
    if not s and not words:
        return []

    # tracking the words
    word_count = defaultdict(int)
    for i in words:
        word_count[i] += 1

    # sliding window, word length, word count, & results
    sliding_window = len(words) * len(words[0])
    word_length = len(words[0])
    result = []

    # initial sliding iteration of the string
    for i in range(len(s) - sliding_window + 1):
        exists = defaultdict(int)
        j = i
        check = 0
        while j < i + sliding_window:
            word = s[j:j + word_length]
            if word in word_count:
                exists[word] += 1
                if exists[word] > word_count[word]:
                    check = -1
                    break
            else:
                check = -1
                break
            j += word_length
        if check == 0:
            result.append(i)
    return result

print(findSubstring("barfoothefoobarman", ["foo", "bar"]))

Considering you have already gone through the problem description, the solution is to utilize the sliding window technique and iterate the string from left to right until it’s valid. A Python library keeps track of word occurrences in the string “s” based on the requirements. Each index has another loop to iterate substrings utilizing word length to make the process faster.

Time Complexity: O(n * m), where n is the length of the string s and m is the number of words in the words list.
Space Complexity: O(k), where k is the number of unique words in the words list.

Template:

def sliding_window_example(arr, target):
    i = 0
    current_sum = 0
    for j in range(len(arr)):
        current_sum += arr[j]
        
        # Shrink the window as long as the current sum exceeds the target
        while current_sum > target:
            current_sum -= arr[i]
            i += 1

        # Now you can process or check the current window
        print("Current window:", arr[i:j+1])

The size of the sliding window is dynamically adjusted based on conditions. Both pointers (i and j) move independently as you expand and shrink the window.

The sliding window technique is helpful for data structure problems, especially when working with lists and linked lists. Hopefully, this article will help you with the concept of the sliding window technique. Thanks for the read.