The sliding window technique is a powerful approach that can help solve a wide range of problems efficiently. This technique is particularly useful when dealing with arrays, strings, or other sequential data structures where you need to process a subset of elements at a time.
Understanding the Sliding Window Technique
The sliding window technique involves maintaining a window of elements from the input data structure and adjusting the window’s boundaries as we progress through the data. The window can be of fixed size or variable size, depending on the problem at hand. By sliding the window over the data, we can efficiently process the elements within the window and extract meaningful information.
The sliding window technique is often used to solve problems that involve finding subarrays or substrings that satisfy certain conditions. Instead of naively iterating through all possible subarrays or substrings, which can lead to quadratic time complexity, the sliding window technique allows us to solve such problems in linear time complexity.
Problem 1: Maximum Sum Subarray of Size K
Let’s consider a problem where we need to find the maximum sum subarray of a fixed size K within a given array of integers. We can efficiently solve this problem using the sliding window technique. Here’s an example implementation in Swift:
/**
* Time Complexity: O(n), Space Complexity: O(1)
*/
func maxSumSubarray(arr: [Int], k: Int) -> Int {
var maxSum = Int.min
var windowSum = 0
var windowStart = 0
for windowEnd in 0..<arr.count {
windowSum += arr[windowEnd]
if windowEnd >= k - 1 {
maxSum = max(maxSum, windowSum)
windowSum -= arr[windowStart]
windowStart += 1
}
}
return maxSum
}
// Example usage
print(maxSumSubarray(arr: [1, 4, 2, 10, 23, 3, 1, 0, 20], k: 4)) // 39
print(maxSumSubarray(arr: [2, 1, 5, 1, 3, 2], k: 3)) // 9
print(maxSumSubarray(arr: [2, 3, 4, 1, 5], k: 2)) // 7In this example, we define a function maxSumSubarray that takes an array arr and the size of the subarray k as input. We initialize variables to keep track of the maximum sum (maxSum), the current window sum (windowSum), and the starting index of the window (windowStart).
We then iterate through the array using the windowEnd variable. At each iteration, we add the current element to the windowSum. Once the window size reaches k, we update the maxSum if necessary by comparing it with the current windowSum. We then slide the window by subtracting the element at windowStart from the windowSum and incrementing windowStart.
By the end of the iteration, maxSum will hold the maximum sum of any subarray of size k within the given array.
We are using a fixed size sliding window to solve this problem.
Problem 2: Longest Substring Without Repeating Characters
Leetcode Problem: Longest Substring Without Repeating Characters
public class Problem {
public init() {}
/**
* Primary idea: Use a dictionary to hold the next possible valid position of characters of the non-repeating substring,
* and then iterate the string to update maxLen, dictionary, and startIdx encountering duplicates
*
* Time Complexity: O(n), Space Complexity: O(n)
*/
public func lengthOfLongestSubstring(_ s: String) -> Int {
// Max possible length of non-repeating string
var maxLen = 0
// starting the initial point of window to index 0
var startIdx = 0
// Dictionary with key = character, and value = index of the next possible valid position of the character in a non-repeating string
var charToPos = [Character: Int]()
// Convert the string into array of characters for processing
let characters = Array(s)
// Integrate through every character of the string
for (i, character) in characters.enumerated() {
// Checking if we have already seen the element or not
if let pos = charToPos[character] {
// If we have seen the character, move the start pointer
// to position after the last occurrence
startIdx = max(startIdx, pos + 1)
}
// Updating the last seen value of the character
charToPos[character] = i
// Comparing the stored maxLen with the length of the last substring
maxLen = max(maxLen, i - startIdx + 1)
}
return maxLen
}
}
private let solution = Problem()
var s1 = "abcabcbb"
print(solution.lengthOfLongestSubstring(s1)) // 3
var s2 = "bbbbb"
print(solution.lengthOfLongestSubstring(s2)) // 1
var s3 = "pwwkew"
print(solution.lengthOfLongestSubstring(s3)) // 3We are using a variable size sliding window to solve this problem.
Problem 3:
/**
* Time Complexity: O(n), Space Complexity: O(n)
*/
class Solution {
func findAnagrams(_ s: String, _ p: String) -> [Int] {
let countP = p.count
// Convert the strings to arrays of characters
let s = Array(s)
let p = Array(p)
// Array to store the frequency of occurences of a character in String S and P
var arrP = Array(repeating: 0, count: 26)
var arrS = Array(repeating: 0, count: 26)
// Arrat to store the result
var resultArr: [Int] = []
// Update the occurences of every character in P.
for char in p {
arrP[char.indexAsciiValue] += 1
}
// Starting with left pointer at 0
var left = 0
// Move the right pointer to the right in every looping step
for (right, value) in s.enumerated() {
arrS[value.indexAsciiValue] += 1
// Check if the length of the sliding window = length of string P
if right - left + 1 == countP {
if arrP == arrS { // compare the frequency of occurences of 2 arrays. If they are equal => Store the result
resultArr.append(left)
}
// Reset the occurency of the character at the left pointer
// Then move the left point of the window one step forward
arrS[s[left].indexAsciiValue] -= 1
left += 1
}
}
return resultArr
}
}
extension Character {
var indexAsciiValue: Int {
Int(self.asciiValue! - Character("a").asciiValue!)
}
}