using System;

using System.Collections.Generic;

using System.Linq;

public class Program

{

    public static void Main()

    {

        var input = new List<List<string>>

        {

            new List<string>() { "a", "b", "c", "d"},

            new List<string>() { "b", "c", "d"},

            new List<string>() { "e", "b", "c", "a", "d"},

        };

​

        Console.WriteLine("The origin text: \n");

        foreach (var sentence in input)

        {

            Console.Write(string.Join(" ", sentence));

            Console.Write(".");

        }

​

        Console.Write("\n\n");

        Console.WriteLine("Expected output: \n1 a: b \n2 b: c \n3 c: d \n4 e: b \n5 a b: c \n6 b c: d \n7 e b: c \n8 c a: d \n\n ");

        Console.WriteLine("Actual output (the ordering doesn't matter):");

​

        var mostFreuqentOnes = new SentencesParser().GetMostFrequentNextWords(input);

        foreach (var (idx, lhs, rhs) in mostFreuqentOnes.Select((kv, idx) => (idx, kv.Key, kv.Value)))

            Console.WriteLine(idx+1 + " " + lhs + ": " + rhs);

    }

}

​

public class SentencesParser

{

    public Dictionary<string, string> GetMostFrequentNextWords(List<List<string>> text)

    {

        var intermediateCollection = GetIntermediateCollection(text);

​

        return TransformIntermediateToFinal(intermediateCollection);

    }

​

    private Dictionary<string, Dictionary<string, int>> GetIntermediateCollection(List<List<string>> text)

    {

        var intermediateCollection = new Dictionary<string, Dictionary<string, int>>();

        foreach (var sentence in text)

        {

            for (int word = 0; word < sentence.Count; word++)

            {

                if (sentence.Count - word >= 3)

                    UpdateCollection(intermediateCollection, sentence[word] + " " + sentence[word + 1], sentence[word + 2]);

​

                if (sentence.Count - word >= 2)

                    UpdateCollection(intermediateCollection, sentence[word], sentence[word + 1]);

            }

        }

​

        return intermediateCollection;

    }

​

    private Dictionary<string, string> TransformIntermediateToFinal(Dictionary<string, Dictionary<string, int>> twoLevelCollection)

    {

        var result = new Dictionary<string, string>();

        foreach (var (grams, innerGrams) in twoLevelCollection)

        {

            if (!result.ContainsKey(grams))

                result[grams] = "";

​

            int maxFrequencyCount = 0;

            string maxFrequencyString = "";

            foreach (var (word, frequency) in innerGrams)

            {

                if (frequency > maxFrequencyCount

                    || (frequency == maxFrequencyCount

                        && string.CompareOrdinal(maxFrequencyString, word) > 0))

                    (result[grams], maxFrequencyString, maxFrequencyCount) = (word, word, frequency);

            }

        }

        return result;

    }

​

    private void UpdateCollection(Dictionary<string, Dictionary<string, int>> twoLevelCollection, string outerKey, string innerKey)

    {

        if (!twoLevelCollection.ContainsKey(outerKey))

            twoLevelCollection[outerKey] = new Dictionary<string, int>();

​

        if (!twoLevelCollection[outerKey].ContainsKey(innerKey))

            twoLevelCollection[outerKey][innerKey] = 0;

​

        twoLevelCollection[outerKey][innerKey]++;

    }

}