Data Structure: Sliding Window Technique

In the sliding window technique, we maintain a window that satisfies the problem constraints. The window is unstable if it violates the problem constraints, and it tries to stabilize by increasing or decreasing its size.

Following are some of the commonly asked interview questions that use the sliding window technique:

1. Find the longest substring of a string containing `k` distinct characters

Given a string and a positive number `k`, find the longest substring of the string containing `k` distinct characters. If `k` is more than the total number of distinct characters in the string, return the whole string.

2. Find all substrings of a string that are a permutation of another string

Find all substrings of a string that contains all characters of another string. In other words, find all substrings of the first string that are anagrams of the second string.

3. Find the longest substring of a string containing distinct characters

Given a string, find the longest substring containing distinct characters.

4. Find maximum length sequence of continuous ones (Using Sliding Window)

Given a binary array, find the index of 0 to be replaced with 1 to get a maximum length sequence of continuous ones.

5. Find the maximum sequence of continuous 1’s formed by replacing at-most `k` zeroes by ones

Given a binary array, find the maximum sequence of continuous 1’s that can be formed by replacing at most `k` zeroes by ones.

6. Find minimum sum subarray of size `k`

Given an integer array, find the minimum sum subarray of size `k`, where `k` is a positive integer.

7. Find a subarray having the given sum in an integer array

Given an integer array, find a subarray having a given sum in it.

8. Find the smallest subarray length whose sum of elements is greater than `k`

Given an array of positive integers, find the smallest subarray’s length whose sum of elements is greater than a given number `k`.

9. Find the count of distinct elements in every subarray of size `k`

Given an array and an integer `k`, find the count of distinct elements in every subarray of size `k`.

10. Print all subarrays of an array having distinct elements

Given an integer array, print all maximum size subarrays having all distinct elements in them.

11. Count distinct absolute values in a sorted array

Given an array of sorted integers that may contain several duplicate elements, count the total number of distinct absolute values in it.

12. Find duplicates within a range `k` in an array

Given an array and a positive number `k`, check whether the array contains any duplicate elements within the range `k`. If `k` is more than the array’s size, the solution should check for duplicates in the complete array.

Thanks for reading.