Hackerrank: Prefix neighbors

Problem statement

Mark has a dictionary, S, containing n distinct strings. He defines the benefit value of a string as the sum of the ASCII values of its characters.

Mark calls some string A and some string B prefix neighbors if both of the following conditions are satisfied:

1. String A is a prefix of string B.

2. No other string C exists in the dictionary that is both smaller in length than string B and has string A as a prefix.

For example, in S = {"AA", "AB", "ABD", "ABDE"}, the strings AB and ABD are prefix neighbors because AB is a prefix of ABD and no other string of length < 3 in S shares that prefix. The strings ABD and ABDE are also prefix neighbors, but AB and ABDE are not prefix neighbors because string C exists (i.e., ABD).

Mark wants to select a subset of strings from S such that the following conditions are both satisfied:

1. No two strings in the subset are prefix neighbors.
2. The sum of the benefit value of the selected strings is maximal. Given S, help Mark by finding and printing the maximum benefit value he can obtain from a subset of non-prefix-neighbors in S.

Input Format

The first line contains an integer denoting n (the number of strings in the dictionary).

The second line contains n space-separated strings.

Constraints

1 < n <= 4 * \$10^5\$

1 <= \$S_i\$'s length <= 11

Each string contains only uppercase letters.

Output Format

Print the maximum benefit value that Mark can obtain from a subset of non-prefix-neighbors in S.

Sample Input 0

3

A B AE

Sample Output 0

200

Explanation 0

{"A", "B", "AE"}

Strings A and AE are prefix neighbors, so they cannot both be in Mark's subset of S. String B has no prefix neighbor, so we include it in Mark's subset.

To maximize the benefit value, we choose AE and B for our subset. We then calculate the following benefit values for the chosen subset:

Benefit value of AE = 65 + 69 = 134

Benefit value of B = 66

We then calculate and print the total benefit value of our subset, which is 134 + 66 = 200.

My introduction of the algorithm

This is the algorithm to apply trie knowledge and also use maximum weighted independent set knowledge. And the algorithm is one of medium level in February 2017 RookieRank 2 contest.

In the contest, I implemented the trie algorithm but failed test case 10 afterwards.

So, after the contest, I studied the algorithm and one of submissions, write C# code to ask for review. Most of my time is to learn how to implement a trie, and also help myself understand prefix neighbor. The return statement in the function AddWordToTrieByOneCharATime is so confusing, for the test case of string dictionary {"A","ABC"}, the stack of return statements and when the prefix neighbor is set, definitely need better solution in my opinion.

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

/*
 * Problem statement:
 * https://www.hackerrank.com/contests/rookierank-2/challenges/prefix-neighbors
 * 
 * Solution notes:
 * This problem can be solved using Trie and DP. Create a trie from the 
 * given set of strings. 
 * Find the prefix neighbor of each string. Now create a graph such that 
 * each string is a node and there exist a bidirectional edge between two 
 * nodes only if they are prefix neighbors. Now find the maximum weighted
 * independent set.
 * 
 * time complexity: O(N*max_length_of_string)
 * required knowledge: Trie
 * 
 * Maximum weighted independent set:
 * https://en.wikipedia.org/wiki/Independent_set_(graph_theory)
 */
class Solution
{
  /*
   * code review: 
   * How to set up a Trie with 26 children? 
   * n distinct strings are stored in a dictionary, using a data structure Trie. 
   * If the string is in the dictionary, then we mark the string in the Trie as 
   * IsInDictionary, WordInDictionary. 
   * @IsInDictionary - the word is in the original strings
   * @WordInDictionary   - any string in the orginal strings 
   */
   internal class Trie
   {
    public Dictionary<char, Trie> Children { get; set; }
    public bool   IsInDictionary    { get; set; }
    public string LastVisitedWord   { get; set; }

    public Trie()
    {
        Children = new Dictionary<char, Trie>();
        IsInDictionary   = false;
        LastVisitedWord = "";
    }

    /*
     * AddWordToTrieByOneCharATime
     * function is designed to complete the following tasks:
     * Add one word in the dictionary to Trie using recursive function
     * Add one char a time by scanning a word from left to right. 
     * 
     * Tricky part is to set prefix neighbor in the process. 
     * 
     * @index
     * @charArray
     * @word  - 
     * @neighbor - prefix neighbor, it is empty string if there is no prefix neighbor
     * 
     * function return: 
     * Tuple<string, string> - string and its prefix neighbor
     */
    public Tuple<string, string> AddWordToTrieByOneCharATime(
        int    scanIndex, 
        char[] charArray, 
        string word, 
        string neighbour)
    {
        bool isEndOfString = scanIndex == charArray.Length;
        if (isEndOfString)
        {
            IsInDictionary  = true;
            LastVisitedWord = word;

            return new Tuple<string, string>(LastVisitedWord, neighbour);
        }

        char visiting = charArray[scanIndex];

        if (!Children.ContainsKey(visiting))
        {
            Children[visiting] = new Trie();
        }

        // update neighbor string - if IsInDictionary is true, then it is 
        // to set as a prefix neighbor
        return Children[visiting].AddWordToTrieByOneCharATime(
            scanIndex + 1, 
            charArray, 
            word, 
            IsInDictionary ? LastVisitedWord : neighbour);            
    }
  }

  /*
   * study LINQ - GroupBy
   * https://msdn.microsoft.com/en-us/library/bb534304(v=vs.110).aspx
   * 
   * 1. Group string by first char, 26 variations from 'A', 'B', ..., 'Z'
   * 2. For each group, sort strings by string's length in ascending order
   * 3. For example, group of strings starting from char 'A', 
   *    "A","AB","ACD"
   * 4. benefit value is to add all chars' ascii value.   
   */
  static long Process(string[] dict)
  {
    var benefitValue = 0L;                     

    var groupped = dict.GroupBy(x => x[0]);

    // maximum 26 groups, 'A','B', ..., 'Z'
    foreach (var group in groupped)   
    {
        // sort by string's length in ascending order
        var sortedStrings = group.OrderBy(x => x.Length);

        var trie = new Trie();            
        var banned = new HashSet<string>();
        var stack  = new Stack<Tuple<string, string>>();

        foreach (var word in sortedStrings)
        {
            stack.Push(trie.AddWordToTrieByOneCharATime(0, word.ToCharArray(), word, ""));
        }

        // Enumerate the stack, the longest string will be iterated first. 
        // Maximum independent set is kind of greedy as well. 
        foreach (var tuple in stack)
        {
            if (!banned.Contains(tuple.Item1))
            {
                benefitValue += tuple.Item1.ToCharArray().Aggregate(0L, (val, next) => val + (long)next);
                banned.Add(tuple.Item2);
            }
        }
    }

    return benefitValue;
  }

  static void Main(String[] args)
  {
    //ProcessInput();

    RunSampleTestcase2(); 
  }
  /*
   * Trie
   *       A          B
   *     AB
   *   ABC
   *  ABCD 
   *  
   * Things to learn through the debug:
   * How many tries are used in the coding? 
   * Two tries, one is for A started strings: {"A","ABCD"}
   * second one is for B started strings: {"B"}
   */
  static void RunSampleTestcase()
  {
    string[] dict = new string[] { "A", "ABCD", "B" };
    var points = Process(dict);

    Console.WriteLine(points);
  }

  /*
  *  input string[] = new string[]{"A","ABC","AC"}
  * Trie
  *       A          
  *     AB   AC
  *   ABC
  *   
  *  Try to debug the code and figure out how to find prefix neighbor of "ABC". 
  *  How many return calls for "ABC" in the function: 
  *  AddWordToTrieByOneCharATime
  */
  static void RunSampleTestcase2()
  {
    string[] dictionary = new string[] { "A", "ABC", "AC" };
    var points = Process(dictionary);

    Console.WriteLine(points);
  }

  static void ProcessInput()
  {
    var n = Convert.ToInt32(Console.ReadLine());
    var dict = Console.ReadLine().Split(' ');
    var points = Process(dict);

    Console.WriteLine(points);
  }
}