# LeetCode - Longest Substring | Elixir Solution

An Elixir solution for LeetCode's Longest Substring without Repeating Characters problem with detailed explanation and time complexity analysis.

Continuing the short series on LeetCode problem, the third problem involves finding the longest sub-string without repeating characters.

As we understand data structures and efficiency of various operations we can design better algorithms and develop playbooks for working through problems.

## Problem

Given a string `s`

, find the length of the **longest sub-string** without repeating characters.

**Example 1:**

```
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
```

**Example 2:**

```
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
```

**Example 3:**

**Constraints:**

`0 <= s.length <= 5 * 10`

^{4}`s`

consists of English letters, digits, symbols and spaces.

## Solution

```
defmodule Solution do
@spec length_of_longest_substring(s :: String.t()) :: integer
def length_of_longest_substring(s) do
window = {0, 0}
seen = %{}
longest = 0
charlist = String.to_charlist(s)
get_length(s, window, seen, longest, charlist)
end
def get_length(_s, _, _, longest, []), do: longest
def get_length(s, {left, right}, seen, longest, [char | tail]) do
case Map.get_and_update(seen, char, &{&1, right}) do
{prev_pos, new_seen} when is_nil(prev_pos) or prev_pos < left ->
new_longest = max(right - left + 1, longest)
get_length(s, {left, right + 1}, new_seen, new_longest, tail)
{prev_pos, new_seen} ->
new_left = prev_pos + 1
get_length(s, {new_left, right + 1}, new_seen, longest, tail)
end
end
end
```

## TLDR;

- Traverse the string and maintain a
**sliding window**of left and right indices. - Store the index of previously seen chars in a map (HashTable):
`%{char => index}`

- If character at position
`right`

has already been seen, set`left`

to the character's index`+ 1`

. - In any case, increment
`right`

+ 1. - Repeat, keeping max of
`right`

-`left`

.

**Time Complexity: O(N) **

**Source:** https://github.com/tmartin8080/leet

## Approach and Explanation

Let's walk through a simple example where: `s = "aba"`

We start by setting some initial values:

```
# track sliding window
window = {0, 0}
# store characters that have been seen and their indices
seen = %{}
# store the length of the current, longest substring
longest = 0
# store a list of each individual character
charlist = String.to_charlist(s)
```

*These will be used as temporary data structures while we recurse over the input string.*

Next, we call `get_length/5`

to kick off recursion and find the longest substring:

`get_length(s, window, seen, longest, charlist)`

We define the base case as:

When the charlist is empty, we've reached the of the input string

`def get_length(_s, _, _, longest, []), do: longest`

When the base case is reached, we return the `longest`

value.

### Recursion

This function seems complicated, but walking through the example should help clarify what's going on:

Remember our input string: `s = aba`

**First Iteration**

Here are the current values during the first iteration:

```
# current values
def get_length("aba", {0, 0}, %{}, 0, ["a" | tail]) do
```

Then we enter a `case`

clause that will branch logic depending on the result:

The expanded anonymous function returns a `{key, value}`

tuple that will update the map HashTable at key: `a`

with value: `0`

`Map.get_and_update/3`

returns the a two element tuple with the previous `value`

at `key`

and the updated map:

Because the character's previous position is `nil`

, the first guard clause is a match:

```
# prev_pos = nil, new_seen = %{"a" => 0}
{prev_pos, new_seen} when is_nil(prev_pos) or prev_pos < left ->
```

Here we increment the `longest`

value, update the sliding window and call the function again with new values:

**Second Iteration**

The second time around we still have a non-empty list so we enter the recursive clause again with the new values:

Again, because we haven't seen `b`

yet, the first clause of the case statement is matched:

```
# window = {left = 0, right = 1}
case Map.get_and_update(%{"a" => 0}, "b", fn "b" -> {"b", 1} end) do
# prev_pos = nil, new_seen = %{"a" => 0, "b" => 1}
{prev_pos, new_seen} when is_nil(prev_pos) or prev_pos < left ->
```

We update the values and re-call the function:

```
# left = 0, right = 1, longest = 1
new_longest = max(right - left + 1, longest)
# updated values
get_length(s, {0, 1 + 1}, %{"a" => 0", "b" => 1}, 2, ["a"])
```

**Third Iteration**

Notice how the window's `left`

index hasn't moved yet. This is because we have only seen unique characters up to this point.

The third pass has a character we've seen previously:

` def get_length("aba", {0, 2}, %{"a" => 0, "b" => 1}, 2, ["a" | tail) do`

Again, we hit the case statement, but this time `prev_pos`

is not `nil`

:

```
# window = {left = 0, right = 2}
# seen = %{"a" => 0, "b" => 1}
Map.get_and_update(seen, "a", fn "a" -> {"a", 2} end)
# returns
{0, %{"a" => 2, "b" => 1}}
```

This time around, the result will not match the first guard clause:

```
# result = {0, %{"a" => 2, "b" => 1}}
{prev_pos, new_seen} when is_nil(prev_pos) or prev_pos < left ->
```

Because `prev_pos`

is not `nil`

, nor is `0`

less than `0`

. So we'll fallback to the second clause:

```
# result = {0, %{"a" => 2, "b" => 1}}
{prev_pos, new_seen} ->
new_left = prev_pos + 1
get_length(s, {new_left, right + 1}, new_seen, 2, [])
```

This clause increments the window's `left`

index to be the next index after the previously seen position, increments the right index normally but keeps the current longest value and re-calls the function.

## Base Case Result

At this point charlist is an empty list so our base case function head matches:

```
# longest = 2
def get_length(_s, _, _, longest, []), do: longest
```

Given `s = "aba"`

, the longest substring is `ab`

and it's length is `2`

.

## Complexity Analysis

Identify `N`

for algorithm.

`N`

= length of input string.

- Set defaults -
`3 steps`

- For each character, update initial values:
`N * 3 steps`

Gives us approximately: `3 + 3N`

and after dropping constants:

**Time Complexity: O(N) **

## Wrapping Up

These contrived problems can be helpful to understand the performance characteristics for various data structures and developing playbooks for tackling problems.

If you're enjoying the newsletter, please consider subscribing to support my work.

Thanks for reading!

-- Troy

Twitter: @tmartin8080 | ElixirForum