By Troy Martin in Elixir — Feb 12, 2023

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:

Input: s = "pwwkew" 
Output: 3 
Explanation: The answer is "wke", with the length of 3.

Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

0 <= s.length <= 5 * 10⁴
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:

case Map.get_and_update(%{}, "a", fn "a" -> {"a", 0} end) do

Short-hand anonymous function expanded for clarity

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:

{nil, %{"a" => 0}}

There was no value at key "a" in map, so first element is nil

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:

# At this point, we still have initial values:
# left = 0, right = 0, longest = 0
# right - left + 1 = 1
new_longest = max(right - left + 1, longest)

# updated values
get_length(s, {0, 0 + 1}, %{"a" => 0"}, 1, ["b", "a"])

Update values for next iteration

Second Iteration

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

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

Notice the current character is "b"

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"])

💡

This may be difficult to read, but it helps demonstrate how the values change as we step through recursion.

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