Longest Substring Without Repeating Characters

Setup

Mix.install([
  {:benchee, "~> 1.0"}
])

S1

defmodule S1 do
  @spec length_of_longest_substring(s :: String.t()) :: integer
  def length_of_longest_substring(s) do
    for i <- 0..(byte_size(s) - 1), j <- i..(byte_size(s) - 1) do
      String.slice(s, i..j)
    end
    |> Enum.sort_by(&amp;byte_size/1, :desc)
    |> Enum.find(fn s ->
      byte_size(s) == s |> String.to_charlist() |> Enum.uniq() |> length
    end)
    |> byte_size
  end
end

S2

defmodule S2 do
  @spec length_of_longest_substring(s :: String.t()) :: integer
  def length_of_longest_substring(s) do
    recur(s, 0, String.length(s))
  end

  def recur(s, i, len) do
    cond do
      len <= 1 -> len
      i + len > byte_size(s) -> recur(s, 0, len - 1)
      unique?(s, i, len) -> len
      true -> recur(s, i + 1, len)
    end
  end

  defp unique?(_, _, len) when len > 63 do
    false
  end

  defp unique?(s, i, len) do
    s
    |> String.to_charlist()
    |> Enum.slice(i, len)
    |> Enum.frequencies()
    |> Enum.all?(fn {_, v} -> v == 1 end)
  end
end

S2 - optimized use list

defmodule S2OPL do
  @spec length_of_longest_substring(s :: String.t()) :: integer
  def length_of_longest_substring(s) do
    recur(String.graphemes(s), 0, String.length(s))
  end

  def recur(l, i, len) do
    recur(l, i, len, len)
  end

  def recur(l, i, len, length) do
    cond do
      len <= 1 -> len
      i + len > length -> recur(l, 0, len - 1, length)
      unique?(l, i, len) -> len
      true -> recur(l, i + 1, len, length)
    end
  end

  defp unique?(_, _, len) when len > 63 do
    false
  end

  defp unique?(l, index, len) do
    Enum.slice(l, index, len) |> unique?()
  end

  defp unique?([]) do
    true
  end

  defp unique?(l) do
    [c | l] = l

    if unique?(l, c) do
      unique?(l)
    else
      false
    end
  end

  defp unique?([], _) do
    true
  end

  defp unique?([first | _rest], c) when c == first do
    false
  end

  defp unique?([first | rest], c) when c != first do
    unique?(rest, c)
  end
end

S2 - optimized use str

defmodule S2OPS do
  @spec length_of_longest_substring(s :: String.t()) :: integer
  def length_of_longest_substring(s) do
    recur(s, 0, byte_size(s))
  end

  def recur(l, i, len) do
    recur(l, i, len, len)
  end

  def recur(l, i, len, length) do
    cond do
      len <= 1 -> len
      i + len > length -> recur(l, 0, len - 1, length)
      unique?(l, i, len) -> len
      true -> recur(l, i + 1, len, length)
    end
  end

  defp unique?(_, _, len) when len > 63 do
    false
  end

  defp unique?(l, index, len) do
    :binary.part(l, index, len) |> unique?()
  end

  defp unique?("") do
    true
  end

  defp unique?(l) do
    <> <> l = l

    if unique?(l, c) do
      unique?(l)
    else
      false
    end
  end

  defp unique?("", _) do
    true
  end

  defp unique?(<> <> _rest, c) when c == first do
    false
  end

  defp unique?(<> <> rest, c) when c != first do
    unique?(rest, c)
  end
end

S3

from: Idiomatic Elixir using pattern matching and tail recursion

defmodule S3 do
  @spec length_of_longest_substring(s :: String.t()) :: integer
  def length_of_longest_substring(s), do: max_ss(String.graphemes(s), [], 0)

  defp max_ss([], _window, max_len), do: max_len

  defp max_ss([c | chars], window, max_len) do
    {new_window, window_len} = scan(window, c)
    max_ss(chars, new_window, max(max_len, window_len))
  end

  defp scan(window, c, acc \\ [], len \\ 0)
  defp scan([], c, acc, len), do: {Enum.reverse([c | acc]), len + 1}
  defp scan([wc | rest], c, acc, len) when wc != c, do: scan(rest, c, [wc | acc], len + 1)
  defp scan([wc | rest], c, _acc, _len) when wc == c, do: scan(rest, c, [], 0)
end

Unit test

ExUnit.start(autorun: false)

defmodule Test do
  alias S2OPS, as: Solution
  use ExUnit.Case

  test nil do
    assert Solution.length_of_longest_substring("") == 0
    assert Solution.length_of_longest_substring("abcabcbb") == 3
    assert Solution.length_of_longest_substring("bbbbb") == 1
    assert Solution.length_of_longest_substring("pwwkew") == 3

    assert Solution.length_of_longest_substring(
             "wgvgblarjtolsgzdebatyzdksjncyocwwzczkctvyhgqqgwujynhxttpcgscuuyswdsgf"
           ) == 12

    assert Solution.length_of_longest_substring(
             "hijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789hijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789hijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789hijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789hijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789hijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
           ) == 55
  end
end

ExUnit.run()

Bench

s =
  "hijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789hijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789hijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789hijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789hijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789hijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"

Benchee.run(%{
  # "s1" => fn -> S1.length_of_longest_substring(s) end,
  "s2" => fn -> S2.length_of_longest_substring(s) end,
  "s2opl" => fn -> S2OPL.length_of_longest_substring(s) end,
  "s2ops" => fn -> S2OPS.length_of_longest_substring(s) end,
  "s3" => fn -> S3.length_of_longest_substring(s) end
})

Recurion

defmodule Util do
  def sub_strs(s) do
    sub_strs(s, 0, String.length(s))
  end

  def sub_strs(s, _, 1) do
    String.graphemes(s)
  end

  def sub_strs(s, i, len) do
    if i + len > byte_size(s) do
      sub_strs(s, 0, len - 1)
    else
      [String.slice(s, i, len)] ++ sub_strs(s, i + 1, len)
    end
  end
end

Util.sub_strs("abcd")

Recursion with cond

defmodule Util do
  def sub_strs(s) do
    sub_strs(s, 0, String.length(s))
  end

  def sub_strs(s, i, len) do
    cond do
      len <= 1 -> String.graphemes(s)
      i + len > byte_size(s) -> sub_strs(s, 0, len - 1)
      true -> [String.slice(s, i, len)] ++ sub_strs(s, i + 1, len)
    end
  end
end

Util.sub_strs("abcd")

Tail recursion

defmodule Util do
  def sub_strs(s) do
    sub_strs(s, 0, String.length(s), [])
  end

  def sub_strs(_s, _i, 0, acc) do
    acc
  end

  def sub_strs(s, i, len, acc) do
    if i + len > byte_size(s) do
      sub_strs(s, 0, len - 1, acc)
    else
      sub_strs(s, i + 1, len, acc ++ [String.slice(s, i, len)])
    end
  end
end

Util.sub_strs("abcd")

Tail recursion with cond

defmodule Utils do
  def sub_strs(s) do
    sub_strs(s, 0, String.length(s), [])
  end

  def sub_strs(s, i, len, acc) do
    cond do
      len == 0 -> acc
      i + len > byte_size(s) -> sub_strs(s, 0, len - 1, acc)
      true -> sub_strs(s, i + 1, len, acc ++ [String.slice(s, i, len)])
    end
  end
end

Utils.sub_strs("abcd")