The Day I Was Beaten by the Sliding Window Algorithm

If you’re a developer or studying to become one, you’ve likely encountered algorithms. But if you’re not familiar with them yet, don’t worry! Algorithms are essentially step-by-step procedures designed to solve specific problems. Think of them as a series of instructions that guide you to a solution.

Given how many algorithms exist, it’s nearly impossible to memorize them all. It’s completely normal to come across algorithms you’re unfamiliar with—even seasoned developers do. That was exactly my experience when I first encountered the sliding window algorithm.

The Length of Longest Substring Exercise

Before I dive into how I discovered the sliding window algorithm, let me first talk about the problem that led me there: the Length of the Longest Substring exercise.

The problem goes something like this: Given a string, you need to find the length of the longest substring without repeating characters. For example, if you’re given the string abcabcbb, the longest substring without repeating characters is abc, which has a length of 3.

At first glance, this might seem simple, but as I started working through different test cases, I realized it was more complex than I initially thought. The challenge was figuring out how to efficiently track substrings and detect when characters started repeating.

First Solution: The Brute-Force Approach

Like many developers, my first attempt to solve the Length of the Longest Substring problem was with a brute-force approach. The idea seemed simple enough:

1. Run a loop for each character in the string;
2. Check if the current substring already contains the character;
   • If the character was not added before, just append it to the newSubstring variable;
   • If it already contains the character, then append the newSubstring to the substrings array, clear the newSubstring variable and then append the character to the newSubstring;
3. After running the loop, check for the longest substring using max and count.

func wrong_lengthOfLongestSubstring(_ string: String) -> Int {
    guard string.count >= 1 && string.count <= 10_000_000 else { return 0 }
    var substrings: Array<String> = []
    var newSubstring: String = ""
    for char in string {
        if newSubstring.contains(char) {
            substrings.append(newSubstring)
            newSubstring = String()
        }

        newSubstring.append(char)
    }

    substrings.append(newSubstring)

    return substrings.max(by: { $0.count < $1.count })?.count ?? 0
}

The idea here was. just to generate an array of substrings without repeated characters and then filter for the longest. It works, but that’s not an efficient solution for some reasons:

1. It has a lot of loops:
   • The loop that build the substrings;
   • The .contains() method that will loop for each character in the newSubstring variable;
   • the .max() method that will loop the substrings array.
2. It resets the newSubstring instead of trying to skip or reuse something

Well, this code was not good enough, so I had to make some changes in order to make it more efficient

Improving the code

The first improvement I made in this solution was eliminating the need for variables to store the current substring and the array of substrings. Instead, I introduced variables to track the maximum substring length (maxSum), the length of the current substring (currentSum), and a dictionary (characterMap) to count the occurrences of each character.

This approach simplifies the logic by focusing on character counts and substring lengths, reducing the need for unnecessary storage of intermediate substrings.

func wrong_lengthOfLongestSubstring_secondAttempt(_ string: String) -> Int {
    guard string.count >= 1 && string.count <= 10_000_000 else { return 0 }

    var maxSum: Int = 0
    var currentSum: Int = 0
    var characterMap: [Character : Int] = [:]

    for char in string {
        characterMap[char, default: 0] += 1

        if characterMap[char, default: 0] > 1 {
            if currentSum > maxSum { maxSum = currentSum }
            currentSum = 0
        }

        currentSum += 1
    }

    if currentSum > maxSum { maxSum = currentSum }

    return maxSum
}

That solved a lot of the problems of the first version of the code, but there is still one problem: It doesn’t try to skip or reuse values, it keeps resetting the currentSum.

This was the best result I could achieve without searching for any hints. But, as good as it was, one stubborn problem still lingered in the code. It just wasn’t cutting it for me. So, finally, I decided it was time to go hunting for a better solution.

I opened up GPT, typed in my prompt, and… Boom! It hit me with a brand-new (to me 😅) algorithm: the Sliding Window. An absolute game-changer.

The Sliding Window Technique

The Sliding Window technique is an efficient way to solve problems involving arrays or strings, especially when you’re looking for arrays or substrings. Instead of repeatedly recalculating values from scratch, you use a “window” (a range of elements) that slides across the data.

In our case, we’re checking for the longest substring without repeating characters, the window starts small and expands until a duplicate is found. Then, instead of restarting, you just adjust the window by “sliding” the starting point forward, making it much more efficient than brute force approaches.

And that was the final solution:

public func lengthOfLongestSubstring(_ string: String) -> Int {
    guard string.count >= 1 && string.count <= 10_000_000 else { return 0 }
    
    var maxSum: Int = 0
    var start: Int = 0
    var characterMap: [Character : Int] = [:]
    
    for (index, char) in string.enumerated() {
        if let previousIndex = characterMap[char], previousIndex >= start {
            start = previousIndex + 1
        }
        
        characterMap[char] = index
        
        let currentSum = index - start + 1
        maxSum = max(maxSum, currentSum)
    }
    
    return maxSum
}

Pretty cool, huh?

Conclusion

And there you have it — my adventure from brute-forcing my way through code, getting stuck with a problem, to finally discovering the almighty Sliding Window! It’s like I went from using a butter knife to cut a tree to finding a chainsaw hidden in my toolbox all along.

Well, that was the day I was beaten by the Sliding Window algorithm. Now, you and I both know how the sliding window works. Will you ever use it for something? Maybe… maybe not, because, well, life’s unpredictable like that. But hey, it’s still a pretty cool solution to this problem, right?

Have you used the sliding window technique before? Or maybe you’ve got an even cooler solution? Let me know in the comments!