Hallo vrienden en familie, Leo hier. Today we will solve an interesting algorithm called Longest Substring Without Repeating Characters in Swift.

That algorithm is solved with a very common tactic on algorithmic challenges called the “Sliding Window” technique/pattern. But what is that?

The sliding window pattern consists in create a range, with beginning and end, that your answer is easily processed there. In our case, we will create a sliding window (a range of characters) that embraces our answers, and for each one of the new characters, we can compute if the window is still valid.

No more talking, let’s code! But first…  

Painting of The Day

The painting I chose is called Still Life at the Open Window by Juan Gris, 1925.

Juan Gris is recognized along with Pablo Picasso, Georges Braque, and Fernand Léger as one of the four major figures in Cubism, the avant-garde 20th-century art movement that revolutionized European painting and sculpture. Gris was born in 1887 in Madrid, where he later studied engineering from 1902 to 1904.

I chose this painting because as we are talking about the sliding window pattern, how about a cubism painting about windows?  

The Problem – Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

Today we will solve the leetcode problem number 3 in Swift. This is not a trivial medium problem. At first, looks simple but you will see that we will have to use some tricks to get this done. First, let’s describe the pseudo-algorithm of the sliding window solution.

1. First, initialize two pointers one for the first character and one for the second.
2. Create an additional hashmap structure to be our data structure to validate if every new character is unique. This hashmap will be [String:Bool], where we just need to put the characters that we need there and we can check in O(1) if they are unique.
3. Then we will traverse the tree while the end pointer is smaller than the string array.
4. For each iteration, we will read the current value of the end pointer character.
5. If the hashmap we create in Step 2 doesn’t contain the new read character, we will add that character to the hashmap and update the max window value.
6. If the hashmap we create in Step contains the new read character, we will have to manipulate the window size.
   1. First, we check where is the last invalid start for the new window. We do that by checking where is the same character inside the window. For example, if the window is “baca” the next valid window will be “ca”, we do that by checking every letter from the beginning until it is not the end letter or the start and end being the same index. Essentially here we are discarding all the first entries that don’t create a new valid window.
   2. Then we remove all entries of the hashmap created in step 2.
   3. Update the start to be one more of the last invalid we found in step 6.1 (start pointer will become the first valid)
   4. Create a new hashmap with the updated window.
7. Update the end pointer giving it plus one.

And looks a lot, but in code is not that hard. I would say medium difficulty.  

Sliding Windows Types

Now you know why the name of the pattern is sliding window.

A visualization of this algorithm for the string “ABCADK” would be: 

Observe that the red is the window, and it shrinks and grows conforming to our algorithm goal.

There are two types of problems with sliding windows, fixed windows, and dynamic windows. Our problem is the type of dynamic window because we don’t know what would be the window size.

Code Solution – Sliding Window Pattern in Swift

Now check the code below and I will indicate in the algorithm all the steps of the pseudo-algorithm above with comments. For example, mark 1 is the 1 in the pseudo-algorithm, mark 2 is the second point in the pseudo-algorithm, and so on.  

class Solution {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        let arrayS = s.map {"\($0)"}
        if s.isEmpty { return 0}
        if s.count == 1 { return 1 }
        var unique = [String:Bool]() // mark 2
        var maxWindow = 1
        
        var start = 0 // mark 1
        var end = start + 1 // mark 1
        
        unique[arrayS[start]] = true // mark 2
        
        while end < arrayS.count { // mark 3
            if unique[arrayS[end]] == nil { // mark 4
                unique[arrayS[end]] = true // mark 5
                maxWindow = max(maxWindow, unique.count) // mark 5
            } else { // mark 6
                while arrayS[start] != arrayS[end] || start == end { // mark 6.1
                    start += 1
                }
                
                unique.removeAll() // mark 6.2
                start += 1 // mark 6.3
                
                for x in start...end { // mark 6.4
                    unique[arrayS[x]] = true
                } 
            }
           end += 1 // mark 7
        }
        
        return maxWindow
    }
}

That’s it!

Solving without Sliding Window

If you don’t like the sliding window pattern, you can solve it using dynamic programming. With DP you can save the last valid start position and calculate your longest based on start position only. Check the solution below:  

class Solution {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        var longest = 0
        var startIndex = 0
        var charMap = [Character: Int]()

        for (index, char) in s.enumerated() {
            if let foundIndex = charMap[char] {
                startIndex = max(foundIndex+1, startIndex)
            }
            longest = max(longest, index - startIndex + 1)
            charMap[char] = index
        }

        return longest
    }
}

Also solves the problem, with even fewer lines of code.  

Continue Studying Algorithms

Working with arrays is not enough to get through the algorithms interviews in big techs, you also have to know linked lists. And to practice that you can try the odd even problem in this article. We study there how to manipulate a linked list separating its parts without the need to create an additional data structure.

Studying the basics is never a waste of time, and nothing more ground knowledge than the classic merge sort algorithm in Swift. In this article, we explore one way to implement that legendary algorithm in Swift and how you could improve a little bit your knowledge of divide and conquer algorithms.  

Summary

Today we check two solutions for a very common problem in Leetcode. One uses the sliding window technique and another one uses dynamic programming. Study both and see which one your brain adapts the best. The sliding window is a powerful technique to have in Swift algorithm interviews and today we studied one of its classic implementations of it.

Fellow developers, that’s all. I hope you liked reading this article as much as I enjoyed writing it. If you want to support this blog you can Buy Me a Coffee or just leave a comment saying hello. You can also sponsor posts! You can reach me on LinkedIn, or Twitter or send me an e-mail through the contact page.

Thanks for the reading and… That’s all folks.

Image Credit: Wikiart