LeetCode - Longest Palindromic Substring | Elixir Solution

This time around we have a different type of problem, one involving strings/binaries and palindromes which are words that spell the same words in reverse: noon.

Likey many of these problems, they seem simple at first glance. As you dig into them however, you find that improving performance over a brute-force approach takes some careful consideration.

Problem

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad" 
Output: "bab" 
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd" 
Output: "bb"

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

Elixir Solution

defmodule Solution do
  @spec longest_palindrome(s :: String.t()) :: String.t()
  def longest_palindrome(s) when s == "" or is_nil(s), do: ""

  def longest_palindrome(s) when is_binary(s) do
    {chars, n} = to_map(s)
    find_longest({s, chars, n}, 0, {0, 0})
  end

  defp find_longest({s, _chars, n}, index, {left, right}) when index > n do
    String.slice(s, left..right)
  end

  defp find_longest(data, index, longest) do
    longest = expand_range(data, index, index, longest)
    longest = expand_range(data, index, index + 1, longest)
    find_longest(data, index + 1, longest)
  end

  defp expand_range({_s, _chars, n} = data, left, right, longest) when left == right do
    new_left = max(left - 1, 0)
    new_right = min(right + 1, n)
    expand_range(data, new_left, new_right, longest)
  end

  defp expand_range({_s, chars, n} = data, left, right, longest) when left >= 0 and right <= n do
    if Map.get(chars, left) == Map.get(chars, right) do
      new_longest = update_longest({left, right}, longest)

      expand_range(data, left - 1, right + 1, new_longest)
    else
      longest
    end
  end

  defp expand_range(_data, _left, _right, longest), do: longest

  # keep first one found
  defp update_longest({a, b}, {c, d} = longest) when d - c >= b - a, do: longest
  defp update_longest(new, _longest), do: new

  defp to_map(s) do
    s
    |> String.codepoints()
    |> Enum.reduce({%{}, 0}, fn char, {map, index} ->
      new_map = Map.put(map, index, char)
      {new_map, index + 1}
    end)
  end
end

TLDR;

1. Convert String to Map for efficient random access (vs Linked List).
2. Iterate over each char to expand_range (Expand Around Center).
3. expand_range expands while palindrome is found, returns current longest when not found.
4. expand_range is called twice, once for odd and once for even length substrings.

Time Complexity: O(n^2)

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

Check Palindrome  

Let's start by discussing a few ways to determine if a string is a palindrome.  The first can be accomplished by using two pointers and working toward the center:

1. Outside Pointers

Create pointers for the start and end:

Then work toward to the center.  If the strings at low | high positions match, continue inward by incrementing low + 1 and decrementing high - 1.

Code Example:

defmodule TwoPointers do
  def is_palindrome?(s) do
    range = {0, max(String.length(s) - 1, 0)}
    check_pointers(s, range)
  end

  defp check_pointers(_s, {low, high}) when low > high, do: true

  defp check_pointers(s, {low, high}) do
    left = String.at(s, low)
    right = String.at(s, high)

    if left == right do
      check_pointers(s, {low + 1, high - 1})
    else
      false
    end
  end
end

When the two pointers pass each other low > high then we know the string is a Palindrome.

2. Expand Around Center

The second approach is to start at the center:

Then work outward, and at each step check that the characters match:

Once we have checked all character pairs and go beyond the 0 index on the left, the string is a palindrome.

Even-Length Strings

This approach has a quirk though.  When the string length is  odd, we can take the center and move outward,  but when the length of the string is even, there isn't a single center value.  To account for this, we can compare two center-most values:

Then work outward:

With even length strings, once you find the middle characters working outward is the same.  Let's look at a code example for this:

Code Example:

defmodule ExpandCenter do
  def is_palindrome?(s) do
    string_length = String.length(s)
    window = find_center(string_length)
    expand(s, window)
  end

  # we've expanded beyond the left-most index which means 
  # that all steps have passed and the string is a palindrome.
  defp expand(_s, {left, _right}) when left < 0, do: true

  defp expand(s, {left, right}) do
    if String.at(s, left) == String.at(s, right) do
      expand(s, {left - 1, right + 1})
    else
      false
    end
  end

  defp find_center(string_length) do
    if Integer.mod(string_length, 2) == 0 do
      mid = round(string_length / 2)
      {mid - 1, mid}
    else
      mid = round((string_length - 1) / 2)
      {mid, mid}
    end
  end
end

The benefits of either approach above is that there are n / 2 steps when the string is even and n / 2 + 1 when the string length is odd.

Approach - Explanation

Now onto the problem which is finding the longest substring that's a palindrome.  

A brute-force approach might be to find all the possible substrings, check if they're palindromes and take the longest.  We're going to skip this approach because it's too obviously flawed.

We can instead use Expand Around Center by traversing the string and for each character, expand outward until it's no longer a palindrome. Once for a single character and once for the current character and the next.  This allows us to check for odd length palindromes and even length palindromes which we already know how to do.

After we've traversed the entire string return the longest one found.

First Iteration - odd

Using cbbd as an example, we start at index 0 and check if the character is the center of an odd length palindrome:

Expanding here fails on the first iteration because there's no value on the left. So c is our current longest palindrome substring.

First Iteration - even

Next, we check if characters at index 0 and 0 + 1 is the center of and even length palindrome:

This fails right away because c and b don't match.  The current longest palindrome remains c.  We increase the current index by one and continue to the next.

Second Iteration - odd

Checking for an odd length palindrome:

This fails, and so again, we check index and index + 1 for an even length palindrome:

This time, the two center characters form a palindrome but expanding outward fails.  We update the longest palindrome to: bb.

Again, at this point we would update the current index and continue to the end.

Let's skip the third and fourth iteration and jump into the implementation.

Approach - Implementation

As an aside, I bench-marked 3 different implementations for random-access on a 1000 character string:

1. String.at/2
2. :array.get/3
3. Map.get/2

And here are some crude bench-marking results:

Name             ips        average  deviation         median         99th %
map            35.62       28.08 ms     ±6.00%       27.62 ms       36.79 ms
array          19.67       50.83 ms     ±5.01%       50.24 ms       66.59 ms
string        0.0755    13251.50 ms     ±0.00%    13251.50 ms    13251.50 ms

Comparison:
map            35.62
array          19.67 - 1.81x slower +22.75 ms
string        0.0755 - 471.95x slower +13223.42 ms

Memory usage statistics:

Name      Memory usage
map           11.85 MB
array         11.90 MB - 1.00x memory usage +0.0434 MB
string     45856.02 MB - 3868.39x memory usage +45844.16 MB

Strings are charlists which are singly linked lists so random access has to start at index 0 and traverse to the given index.  

Let's start with a map datastructure to improve performance over random access on strings.

Setup

Now that we've selected maps as our workhorse datastructure, we start by guarding against invalid data

def longest_palindrome(s) when s == "" or is_nil(s), do: ""

And initialize data to feed into some recursive functions.  For this example, let's imagine we're using babad as the String input:

def longest_palindrome(s) do
  {chars, n} = to_map(s)
  find_longest({s, chars, n}, 0, {0, 0})
end

...

defp to_map(s) do
  s
  |> String.codepoints()
  |> Enum.reduce({%{}, 0}, fn char, {map, index} ->
    new_map = Map.put(map, index, char)
    {new_map, index + 1}
  end)
end

First we build a map of the string with the index as the key and the character or codepoint as the value: %{0 => "a"} and return max index as well.

Arguments

The first argument passed to find_longest/3 is a tuple of {s, chars, n} which is the input string, the map representation of the string, and the right-most index of the map.  

# s = "babad", chars: %{0 => "b", ...}, n = 4
find_longest({s, chars, n}, current_index, longest)

The second argument is the current index that we're expanding around.

The third argument passed to find_longest/3 is a tuple structure we're using to represent the longest palindrome found.  This contains a left and right index of the string:

# left = 0, right = o
longest = {left, right}

find_longest({s, chars, n}, index, longest)

Base Case

Next we define the base case as:

When the current index is greater than the max available index n we've traversed the entire string.

Here's the base case function:

defp find_longest({s, _chars, n}, index, {left, right}) when index > n do
  String.slice(s, left..right)
end

Once we've gone beyond the right-most index, we slice the string using left | right indices we found while expanding around each character.

Main Recursion

Next, we have our main recursive function that will expand around each character twice.  The first expand_range/4 call checks for odd-length palindromes and the second checks for even-length palindromes:

defp find_longest(data, index, longest) do
  longest = expand_range(data, index, index, longest)
  longest = expand_range(data, index, index + 1, longest)
  find_longest(data, index + 1, longest)
end

We do this to catch all available palindromes while we're visiting an index.

Expand Around Center

We initialized the longest palindrome as {0, 0} and each call to these functions will either leave the longest range alone, or update it to the left | right indices of a newly discovered palindrome.

The odd-length call is handled first when the index is passed twice:

defp expand_range({_s, _chars, n} = data, left, right, longest) when left == right do
  new_left = max(left - 1, 0)
  new_right = min(right + 1, n)
  expand_range(data, new_left, new_right, longest)
end

All single characters are considered palindromes so we expand outward and pass the updated values along to the next function head:

defp expand_range({_s, chars, n} = data, left, right, longest) when left >= 0 and right <= n do
  if Map.get(chars, left) == Map.get(chars, right) do
    new_longest = update_longest({left, right}, longest)

    expand_range(data, left - 1, right + 1, new_longest)
  else
    longest
  end
end

First we check if we're till within the boundaries using guard clauses.  Then we check if the value at index left equals the value at index right.

If the characters match, we call update_longest/2 to determine the longer of the two palindromes or index ranges:

# keep first one found
defp update_longest({a, b}, {c, d} = longest) when d - c >= b - a, do: longest
defp update_longest(new, _longest), do: new

This will determine which value is longer: the current longest or the newly found palindrome.

After updating the temporary storage longest this function calls itself again to continue expanding:

expand_range(data, left - 1, right + 1, new_longest)

In call other cases, we return the current longest index range value: {left, right}.

Returning Result

After traversing the entire string, we slice the value from the longest range:

defp find_longest({s, _chars, n}, index, {left, right}) when index > n do
  String.slice(s, left..right)
end

Which will return "bab" in our example.

Complexity Analysis

1. Convert string to map: n steps
2. Traverse the string expanding twice: 2n

Since expanding a palindrome around its center could take O(n) time, the overall complexity is: O(n^2)

Wrapping Up

These code problems have been helpful in terms of developing patterns and analyzing performance characteristics of different Data Structures.

By working through some of these problems and solutions I'm realizing that there are distinct ideas involving Functional Data Structures based on immutability and there's much to understand about them.

The Erlang/Elixir communities have provided an immensely solid foundation for developing fast, reliable code, but as we have seen through a few of these solutions there are cases where a deeper understanding of how data structures are implemented can inform better decisions about system design.

Thanks for reading!

-- Troy

Twitter: @tmartin8080  | ElixirForum