In this lecture, we will solve actual coding test problems using the sliding window technique. The sliding window is an algorithmic technique for efficiently handling subsets of consecutive elements within an array or list, particularly useful when dealing with sums, maximums, and minimums of intervals.
Problem: Longest Substring
We will address the problem of finding the length of the longest substring that contains only two distinct characters from a given string.
Problem Description
Input: String s Output: Length of the longest substring containing two distinct characters
Example
Input: "abcabcbb" Output: 3 Explanation: The longest substring is "abc," which does not contain two distinct characters, so "bca" or "cab" is the longest substring.
Problem Approach
To solve this problem, we will use the sliding window technique. The sliding window is a technique that uses two pointers to dynamically adjust the range that satisfies specific conditions.
Step-by-Step Approach
Step 1: Initialize Function
First, we initialize a variable to store the length of the string and the result. We set up pointers to represent the start and end of the sliding window.
let s = "abcabcbb" var left = 0 var right = 0 var maxLength = 0 var charFrequency = [Character: Int]()
Step 2: Extend the Window
We move the right pointer one position at a time and record the frequency of the current character. This allows us to know the frequency of characters included in the current window.
while right < s.count {
let currentChar = s[right]
charFrequency[currentChar, default: 0] += 1
right += 1
Step 3: Check Conditions and Shrink the Window
If the number of characters in the string exceeds two, we move the left pointer to adjust the character count. We repeat this process and calculate the window size to update the maximum length whenever specific conditions are satisfied.
while charFrequency.count > 2 {
let leftChar = s[left]
charFrequency[leftChar]! -= 1
if charFrequency[leftChar] == 0 {
charFrequency.removeValue(forKey: leftChar)
}
left += 1
}
maxLength = max(maxLength, right - left)
Step 4: Complete the Function
The completed code through all these steps is as follows:
func lengthOfLongestSubstringTwoDistinct(_ s: String) -> Int {
var left = 0, right = 0, maxLength = 0
var charFrequency = [Character: Int]()
let charArray = Array(s)
while right < charArray.count {
let currentChar = charArray[right]
charFrequency[currentChar, default: 0] += 1
right += 1
while charFrequency.count > 2 {
let leftChar = charArray[left]
charFrequency[leftChar]! -= 1
if charFrequency[leftChar] == 0 {
charFrequency.removeValue(forKey: leftChar)
}
left += 1
}
maxLength = max(maxLength, right - left)
}
return maxLength
}
Step 5: Time Complexity Analysis
The time complexity of this algorithm is O(n). It is efficient because each character is visited only once. The space complexity is O(1) since the maximum character set is fixed.
Conclusion
The sliding window technique is very useful when exploring consecutive parts that satisfy specific conditions. This method can efficiently solve many algorithm problems. Try running the code below in Swift!
let testString = "abcabcbb" let result = lengthOfLongestSubstringTwoDistinct(testString) print(result) // Output: 3
Practice solving more algorithm problems with the sliding window technique learned in this lecture to enhance your skills!