Max character

Directions

Given a string, find the most frequently occurring character. Print the character and the number of times it occurs to the standard output.

Examples

iex(1)> Maxchar.main("Cool beans!")
{"o", 2}

iex(2)> Maxchar.main("hello")
{"l", 2}

iex(3)> Maxchar.main("hiii there 7777")
{"7", 4}

Constraints

The input may be any string of arbitrary length that fits the pattern, ~r{[^A-Za-z0-9_]}. The resulting output may be any data type that satisfies the requirements. The output must contain both the most frequently occurring character and the number of times it occurs. Assuming an input of "aaaaabc", each of the following outputs would be satisfactory:

• ["a", 5]
• {"a", 5}
• "The character, "a", occurs 5 times."
• a-5

Note

The recommended approach to solving coding challenges is to come up with a tentative solution using pseudo code. This will ensure you fully understand the question and you're heading in the right direction. Next, begin breaking the problem into smaller, more focused pieces. Smaller single-purposed functions are easier to reason about and ultimately solve. Once you've reached an acceptable solution, look for opportunities to refactor and improve your code.

Attempt to solve the problem by yourself. Spend approximately 15 minutes coming up with an original solution. There is nothing gained by copy /pasting someone else's solution or skipping straight to the answer. Create a new Elixir file and begin from a blank page. Start typing code, make comments about what you're trying to accomplish. Remember, try to break the problem down into smaller pieces and focus on solving one piece at a time. This is the best way to learn how to code. It's the best way to gain confidence in yourself and your abilities.

You may need to look up some documentation on how a particular function works and that's fine. Have the HexDocs open in a separate tab and refer to it as needed. Don't cheat yourself by copying someone else's solution. By completing the problem and learning organically your brain will make the necessary connections to transform short-term memory into long-term memory. Use the next section for help if you reach an impasse. Finally, or as a last resort, review the solution I've provided. Type it in manually and try to understand what each line of code is doing.

My approach

The MaxChar problem is an excellent problem because it sets the stage for solving many "string" related challenges. A good way to approach this problem is to start at the output and think backwards. We'll need to print out the most frequently occurring character. In order to do this, we'll need to know how many times each character appears in a string. This means we'll need some way of associating each character with a value. That sounds like a key/value store, or Map. We can store each character as a key in the map, while the value represents its number of occurrences. So, now that we know the direction we we're going, let's figure out how to get there.

We know that we begin with a string. From there, we will need to accomplish the following.

1. Break up the string into individual characters
2. Iterate over those characters to create a map of each character and how many times it appears
3. Find the highest number of occurrences
4. Print the character and number of occurrences

We haven't written any code yet but we're well on our way to solving this problem. Notice how the problem is now broken down into four smaller problems. If we solve each of these smaller problems, we should be able to tie them together into a final solution. Let's start by creating a module for our solution.

defmodule Maxchar do
  @moduledoc """
  Given a string, return the character that occurs most frequently
  """
  def main(str) when is_binary(str) do
    # solution goes here
  end

end

We name our module "Maxchar" and provide some module documentation. Next, create a main function where we receive the string argument and use a guard clause to verify its type. With the boilerplate out of the way it's time to focus on the first step. To break up the string and turn it into a list of characters we'll reach for the graphemes/1 function in the String module. This should serve us nicely.

# extracted from the Maxchar module
def main(str) when is_binary(str) do
  str
  |> count_chars()
end

defp count_chars(string) do
  count_chars(String.graphemes(string), Map.new())
end

In our main function we begin by piping the string to a private function, count_chars. This is a common practice in Elixir. We use the pipe operator to avoid having to create temporary variables and we extract the logic into a private function so that our main function remains succinct and readable. We want to keep our functions short and if possible, with a single purpose.

The count_chars/1 function calls a function of the same name with an arity of 2, passing in a list of characters and an empty map. This sets us up to perform step two, iterate over the characters and count the occurrance of each one.

# extracted from Maxchar module

 defp count_chars([first | rest], map) do
    case Map.has_key?(map, first) do
      true ->
        map = Map.update!(map, first, fn val -> val + 1 end)
        count_chars(rest, map)

      false ->
        map = Map.put_new(map, first, 1)
        count_chars(rest, map)
    end
  end

The count_chars/2 function receives a list of characters and an empty map. We use pattern matching in the function head to bind the first character to the variable "first", the rest of the characters to the variable "rest", and the empty map to the variable "map". For reference, let's use iex to check what the incoming arguments might look like.

# what the result of String.graphemes looks like
iex(1)> string = "hello"
"hello"
iex(2)> String.graphemes(string)
["h", "e", "l", "l", "o"]

# what Map.new looks like
iex(3)> map = Map.new
%{}

As we can see, count_chars/2 will receive a list of characters and empty map. After pattern matching on the input values, we use a case statement inside the function. The purpose of the case statement is to determine if a letter has occurred before or not. It does this by checking the "first" character against the current value of "map". If a letter has occurred before, the true clause will run. If not, then the false clause will run. In either case, the function calls itself passing in the rest of the letters and the updated map. This is a recursive function. It will continue to call itself, each iteration will have a different character in the "first" position. Then the case statement will once again determine if it's a new character or not and update the "map" accordingly.

Now let's look at the individual clauses. If the character in the "first" position is currently in the map, the true clause runs. This will result in the "map" being updated. The character in the "first" position has some value associated with it because it has occurred before. Therefore, we update the map by incrementing that value by one. Lastly, we call the function again passing in the "rest" of the characters and the updated map. If the character in the "first" position is not currently in the map, then it is now making its first appearance. The false clause executes and updates the map by assigning the "first" value as a key and setting its value to 1. The reason the value is set to 1 is because it is the first time the character has occurred. Lastly, the function recurses passing in the "rest" of the characters and an updated map. If the same character were to occur again, the true clause would execute, incrementing the value by 1. This would result in a new value of 2 after the character occurred two times, exactly the behavior we want. We aren't done yet. We need a way to stop the recursive function. What happens when the "rest" of the characters run out. After we iterated through every character and we have a map of characters and their occurrences we will be left with an empty map. We need to account for this.

# extracted from Maxchars
# the following function should be placed ABOVE count_chars/2
  defp count_chars([], map), do: map

Once we reach an empty list, simply return the map. At this point what does our map look like? We can add a call to IO.inspect map to find out.

# passing in "hello"
%{"e" => 1, "h" => 1, "l" => 2, "o" => 1}

Great! We are almost finished. We now have a map of characters with their number of occurrences, in no particular order. The last thing have to do is figure out some way of iterating through the map and pulling out the character that appears most frequently. Remember, we want to return both the key (the character) and the value (the number of occurrences). After some research on the Enum module, the function max_by/2 seems to fit our needs. We'll pass our enumerable (map) as the first argument and an anonymous function as the second argument. We can extract this last piece into a private function. Here is the module in full:

defmodule Maxchar do
  @moduledoc """
  Given a string, return the character that occurs most frequently
  """
  def main(str) when is_binary(str) do
    str
    |> count_chars()
    |> print()
  end

  defp count_chars(string) do
    count_chars(String.graphemes(string), Map.new())
  end

  defp count_chars([], map), do: map

  defp count_chars([first | rest], map) do
    case Map.has_key?(map, first) do
      true ->
        map = Map.update!(map, first, fn val -> val + 1 end)
        count_chars(rest, map)

      false ->
        map = Map.put_new(map, first, 1)
        count_chars(rest, map)
    end
  end

  defp print(map) do
    map
    |> Enum.max_by(fn {char, value} -> value end)
  end
end