Don’t covert the swift string to an array — a solution to Longest Substring Without Repeating Characters

A while back I was trying to solve a few DSA problems like Minimum Window Substring and Longest Substring Without Repeating Characters using swift. Although I had read about how swift string indices are different from that of other collections like arrays due to characters being represented as an extended graphene cluster, but hadn’t used string indexes in action much till that point.
I thought of going the easier route and just converting the input string into a character array, but decided against it. I’ll go through the solution for Longest Substring Without Repeating Characters and try to display how concise our solution can be if we understand how strings and a few operations on them work in swift.

So the problem statement as taken from leetcode is:

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

This is a classic sliding window problem, when we are asked to find a substring or a subarray, it usually can be solved using a sliding window.

The pattern to solve a sliding window problem is to one by one increase the end of the window and then update the start so that the window remains valid.

Here’s my complete solution, I’ll talk through it line by line

My leetcode solution

Looks concise, doesn’t it :)

The better thing is it's very easy to understand too!

So in the first 2 lines, we are just initialising the curWindow and the bestWindow variables. Then we initialise an endIndex variable, which just indicates the end of the window.

Now let’s look at the while loop condition. Here we are going to run the loop till endIndex is not equal to the string’s end index. The while loop is just increasing the end of the window one by one.

NOTE: String’s endIndex is one index after the actual end of the string

The first line inside the while loop is trying to figure out if the current end character is already in the curWindow. We use the range(of :) function, which give the range of a string inside another string. Since we are looking for a character range will not really be a range, it will start and end at the same index. We just use the lower bound of that index.

If it exists that means to add the new character at the end we have to remove all characters till that character in the current window. This is done using removeSubrange, another function that simplifies our work to a great deal here.

Now we append the end characters to the window and compare it to the bestWindow we found till now

Next is a very interesting piece of code:

s.formIndex(after: &endIndex)

With string indexes sadly we can’t just do a += 1 to increase the index. We have to use the function formIndex.

What formIndex does increase the given index to the next string index, it takes in the index as an inout parameter. Be careful to apply it on the string you’re calculating the index for (I was thinking of applying it to the currentWindow once for some reason, so thought I’ll mention it if you fall into the same trap :)).

That is it, just by using a few string functions we were able to solve this very concisely unless obviously, you folks have an even more aesthetic way of solving this, please feel to mention it in the comments.

Hope this post will encourage you to not convert the swift string to an array and save that memory!

Thanks for reading!