Leetcode 49: Group Anagrams - Hash function design talk

Question

problem statement

Given an array of strings, group anagrams together. For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],

Return:

[

["ate", "eat","tea"],

["nat","tan"],

["bat"]

]

Note: All inputs will be in lower-case.

My introduction of algorithm

Understand Hash collision

I came cross the question on this site, and then I started to practice on this algorithm, and gave my code review on timeout issue. One thing I like to emphasis this practice is to design a very good hash function and like to have some discussion as well. Best way to learn is to try to answer people's question, I did try to explain hash collision for a computer programmer using birthday for example, if there are 400 people then there must be at least 2 people has same birthday since there is at most 366 days in a year. You can look up birthday attack if you are interested in advanced topics.

Hash function design concerns

Related to every group of anagrams with lower case alphabetic numbers, any string in the group should be sorted to the same string. How to design your own hash function as a computer programmer? Is it fun to design a good one in algorithm problem solving? There are so many ways to design the hash function, and I just love the freedom of design in algorithm problem solving. You do not want to have hash collisions, in other words, your task is to avoid that different group of anagrams hash to the same thing.

Freedom of design

For example, work on the simple string "abc", the first intuitive idea is to concatenate a string using 01-11-21, first char 0 of substring 01 represents for 'a', second char 1 of "01" expresses only 1 of 'a'. In maximum, there are 26 alphabetic number, I choose to use '-' to separate each char's hashing result.

Further simplify the hash function, I omit the number to represent the char of alphabetic number, since counting delimiter char '-' can help to identify the alphabetic number in the string "abcdefghijklmnopqrstuvwxyz".

In the end, "abc" will be hashed to a key "1-1-1-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0". I like to reserve at least two chars for each alphabetic number.

Test cases

One test case is added to verify hash function key string.

Timeout concern in the design

The idea to avoid timeout issue is to generate a key for each anagram group using O(N) time complexity, instead of naive one by sorting the string, N is the string's length. To take advantage of alphabetic number only has constant of size 26, go through the string once, one char a time, to record the number of occurrence, like a counting sort.

To choose a more efficient sort - counting sort instead of comparison based sorting is the important decision in my practice, I read the question from another practice Leetcode 49 and bet that bottleneck is the string sorting issue.

My wishful thinking

So, I read through some of discussion of group of anagrams questions on this site, and then I like to emphasis this hash function design in my question, hopefully it brings the community some thoughts about hash function in algorithm problem solving.

Here is the C# code passing all test cases on Leetcode online judge. No time out issue. Please help me review.

using System;
using System.Collections.Generic;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode49_GroupAnagrams
{
  public class HashKeys
  {
    /* O(n) solution 
     * abc 
     * hashed to key:
     * 01-11-11
     * 0 stands for a, 1 is count of a
     * further simplify the key:
     * 1-1-1
     * first 1 is count of a, 
     * second 1 is count of b, 
     * third 1 is count of c
     * 
     * In the end, "abc" hashed key will be 
     * "1-1-1-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0"
     */
    public static string ConvertHashKeys(string input)
    {
        if (input == null || input.Length == 0)
        {
            return string.Empty;
        }

        int[] countAlphabetic = new int[26];

        foreach (char c in input)
        {
            countAlphabetic[c - 'a']++;
        }

        return String.Join("-", countAlphabetic);
    }
  }

  class Program
  {                
    /*
     * Leetcode 49 - group anagrams
     * https://leetcode.com/problems/anagrams/
     * 
     */
    static void Main(string[] args)
    {
        RunTestcaseHashfunction();
        RunSampleTestcase();             
    }

    public static void RunTestcaseHashfunction()
    {
        var key = HashKeys.ConvertHashKeys("abc");
        Debug.Assert(key.CompareTo("1-1-1-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0") == 0);

        // "xaba" and "xbaa" are anagrams, both are sorted 
        // to "aabx" in ascending order, but we prefer not to sort the string
        // because of time complexity concern. 
        var key2 = HashKeys.ConvertHashKeys("xaba");
        Debug.Assert(key2.CompareTo("2-1-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-1-0-0") == 0);

        var key3 = HashKeys.ConvertHashKeys("xbaa");
        Debug.Assert(key3.CompareTo("2-1-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-1-0-0") == 0);
    }

    public static void RunSampleTestcase()
    {
        string[] input = new string[]{"ape","and","cat"}; 

        GroupAnagrams(input);
    }

    public static IList<IList<string>> GroupAnagrams(string[] strs)
    {
        var groupAnagrams = new List<IList<string>>(); 

        var groupAnagramsWithKeys = new Dictionary<string, IList<string>>(); 

        foreach(string s in strs)
        {
            string key = HashKeys.ConvertHashKeys(s); 
            if(groupAnagramsWithKeys.ContainsKey(key))
            {
                var anagrams = groupAnagramsWithKeys[key]; 
                anagrams.Add(s); 
                groupAnagramsWithKeys[key] = anagrams; 
            }
            else{
                var anagrams = new List<string>(); 
                anagrams.Add(s); 
                groupAnagramsWithKeys.Add(key, anagrams); 
            }
        }

        foreach(var value in groupAnagramsWithKeys.Values)
        {
            groupAnagrams.Add(value); 
        }

        return groupAnagrams; 
    }
  }
}

Answer 1

Not really a hash

As rolfl pointed out in the comments, what you are generating isn't exactly a hash code. It's more like generating a unique key for each unique anagram. This key can then be used to insert/lookup in a hash set.

Choice of key

The obvious choice of key is just the sorted string. For example, "apple" would have a key of "aelpp". Your choice of key has advantages over sorted strings for large strings. If \$n\$ is the string length, the sorted string uses \$O(n)\$ space but your string uses \$O(\log n)\$ space. But your key uses a minimum of 51 bytes, so for small strings it is more inefficient.

Improvements on key format

One thing you could do is to omit counts for characters that do not appear in the string. To do this, you will need to use the characters themselves as delimiters instead of dashes. For example, "apple" would become "a1e1l1p2".

Another thing that you could do to improve upon the previous format is to omit the count of 1 for single characters. For example "aelp2". This key format is never longer than the original string, and is still logarithmic in space for long strings.

Answer 2

This is the first time I answer one of my questions. Maybe I should make it a community wiki :-).

Hash function design

I did appreciate JS1 and all others help me to practice this algorithm. I did study one hour to go over hash function basic concepts after JS1's review, and reviewed one of the hash function's study I did after one of Hackerrank string problem - Sherlock and anagram in March 27, 2016.

I chose the same hash function as following:

public static string ConvertHashKeys(string s)
{
  if(s == null)
  {
    return string.Empty; 
  }

  var countAlphabetic = new int[26];
  for (int i = 0; i <= s.Length; i++)
  {
    countAlphabetic[s[i] - 'a']++;
  }

  int key = 0;                  
  for (int i = 0; i < 26; i++)
  {
    key = key * 701 + countAlphabetic[i];
  }

  return key.ToString();
}

I ran the submission again and it works for Leetcode online judge. I also questioned myself about hash function design last year, should I focus on the study of computer science or mathematics, cryptographic hash function? 701 is a prime number.