Learn Sliding Window Technique

Introduction

The Sliding Window Technique is a powerful method used in DSA to solve problems involving subarrays or substrings efficiently. It maintains a window that slides over the array or string to process a subset of elements. Window Size can be fixed or variable depending on problem requirements.

Below is the c# code snippet to explain.

Types of Sliding Windows
 

1. Fixed Size Window

Finding the maximum sum of a subarray of size ( k ).

public static int MaxSumSubarray(int[] arr, int k)
{
    int n = arr.Length;

    int maxSum = 0;
    for (int i = 0; i < k; i++)
    {
        maxSum += arr[i];
    }
    int windowSum = maxSum;
    for (int i = k; i < arr.Length; i++)
    {
        windowSum += arr[i] - arr[i - k];
        maxSum = Math.Max(windowSum, maxSum);
    }
    return maxSum;
}

The MaxSumSubarray method finds the maximum sum of any subarray of size ( k ) within a given array. It uses the sliding window technique to achieve this efficiently.

1. Initialization
   • n is the length of the array.
   • maxSum is initialized to 0 and will store the maximum sum of subarrays of size ( k ).
2. Initial Window Sum: The first loop calculates the sum of the first ( k ) elements of the array and stores it in maxSum.
3. Sliding the Window
   • windowSum is initialized to maxSum.
   • The second loop slides the window one element at a time from the ( k )-th element to the end of the array.
   • For each new position of the window, it updates windowSum by subtracting the element that is left behind and adding the new element that enters the window.
   • It then updates maxSum to be the maximum of windowSum and the current maxSum.
4. Return Result: Finally, the method returns maxSum, which is the maximum sum of any subarray of size ( k ).

int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int k = 3;
Console.WriteLine("Maximum sum of a subarray of size " + k + " is " + MaxSumSubarray(arr, k));

Below is the O/P

Time Complexity: O(n)

2. Variable Size Sliding Window

Example. Finding the longest substring with unique characters.

public static int LengthOfLongestSubstring(string s)
{
    int n = s.Length;
    int maxLength = 0;
    int start = 0;
    int end = 0;
    Dictionary<char, int> dict = new Dictionary<char, int>();

    for (end = 0; end < n; end++)
    {
        char currentChar = s[end];
        if (dict.ContainsKey(currentChar) && dict[currentChar] >= start)
        {
            start = dict[currentChar] + 1;
        }
        dict[currentChar] = end;
        maxLength = Math.Max(maxLength, end - start + 1);
    }
    return maxLength;
}

• Initialization
  • n: The length of the string s.
  • maxLength: The length of the longest substring found so far, initialized to 0.
  • start: The starting index of the current window is initialized to 0.
  • end: The ending index of the current window, initialized to 0.
  • dict: A dictionary to store the last index of each character encountered.
• Iterate Through the String: The for loop iterates through each character in the string using the end index.
• Current Character
  • currentChar: The character at the current end index.
• Check for Repeating Characters: If currentChar is already in the dictionary and its last occurrence is within the current window (dict[currentChar] >= start), move the start index to the right of the last occurrence of currentChar (start = dict[currentChar] + 1).
• Update Dictionary: Update the dictionary with the current index of currentChar (dict[currentChar] = end).
• Update Maximum Length: Calculate the length of the current window (end - start + 1) and update maxLength if this length is greater than the current maxLength.
• Return Result: After the loop completes, return maxLength, which is the length of the longest substring without repeating characters.

Time Complexity: O(n)