# Kotlin Algorithm Challenge #2

The following problem is the Longest Substring Without Repeating Characters problem on LeetCode.

# Problem

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

Thereâ€™s one nice example that comes up in the submissions that highlights an edge case as well, which is:

# Solution

When weâ€™re iterating through the array, and evaluating whether a new substring should be the max substring, we need to know two things:

• the length of the current max substring
• what characters are included in the current substring

Once we have those two things, itâ€™s just a matter of iterating through the array once, and itâ€™s not so complicated.

Getting the current max is simple, itâ€™s just a matter of maintaining a max, initialized at 0, and update it as we go through the array.

## Getting the current substring

This part is a little bit more complicated.

Say weâ€™re iterating through the above string. Weâ€™re at position j. The current substring weâ€™re looking at is everything up until i.

If we can easily find i, then the length of the current substring is simply j - i. But how do we find i?

Speaking generally, i is the last occurrence of any char in our current substring.

We can break that into two cases:

1. i is the index of the last occurrence of the char we are currently sitting at, as we iterate through.
2. i is the index of the last occurrence of any other char in the current substring

Iâ€™ve renamed `i` to `lastRepeat`, because what it actually represents is the last repeat of any char in the current substring.

Here is the final code:

# Complexity

Weâ€™re iterating through the array once, so the time complexity is `O(n)`.

The space usage is constant, because while we do have a hashmap, the maximum number of keys is limited by the total number of ASCII characters.

One final note:

It turns out, `forEachIndexed` is less efficient than a simple for loop, e.g.

Note that weâ€™re talking in nanoseconds hereâ€”I definitely think the readability gains from Kotlinâ€™s functional APIs are worth a few extra nanoseconds.

Wow! You read the whole thing. People who make it this far sometimes want to receive emails when I post something new.

I also have an RSS feed.