using System;

using System.Collections;

using System.Collections.Generic;

// C#

public class Solution {

    public static void Main(String[] args) {        

        int numCompetitors = 6;

        int topNCompetitors = 4;

        String[] competitors = {"newshop", "shopnow", "afshion", "fashionbeats", "mymarket", "tcellular"};

        int numReviews = 6;

        String[] reviews = {"newshop is providing good services in the city; everyone should use newshop", "best services by newshop", "fashionbeats has great services in the city", "i am proud to have fashionbeats", "mymarket has awesome services", "Thanks Newshop for the quick delivery afshion"};                

        List<String> result = GetTopCompetitors(numCompetitors, topNCompetitors, competitors, numReviews, reviews);

       foreach(var r in result)

       {

          Console.Write(r + " ");

       }

       Console.WriteLine();

    }

    public static List<string> GetTopCompetitors(int numCompetitors, int topNCompetitors

                                                 , String[] competitors, int numReviews, String[] reviews) 

    {

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

        // add all competitors into HashMap

        for(int i=0; i<numCompetitors; i++) {

            map.Add(competitors[i].ToLower(), 0);

        }

        // O(N)

        // loop through all reveiws

        foreach(String review in reviews) {

            String[] words = review.ToLower().Split(' ');

            var used = new HashSet<string>();

            // loop through all words in a review

            foreach(String word in words) {

                if(map.ContainsKey(word)

                   && used.Add(word)) {

                    map[word] = map[word] + 1;

                }

            }

        }

​

       // Create list of { competitor, frequency } objects

      var k=0;

      var itemFreqList = new ItemFrequency[map.Keys.Count];      

      foreach(var key in map.Keys)

      {

             itemFreqList[k++] = new ItemFrequency(key, map[key]);

      }

​

      // Sort the list from high to low frequency      

      Array.Sort(itemFreqList, (x,y) => { 

        return x.Frequency == y.Frequency ?

                 x.Key.CompareTo(y.Key):

                 y.Frequency.CompareTo(x.Frequency);  

      });

      var result = new List<string>();      

      for(int i=0; i<topNCompetitors && i<itemFreqList.Length; i++){

          result.Add(itemFreqList[i].Key);

      }   

​

      return result;

  }

} 

​

public class ItemFrequency

{

   public ItemFrequency(string key, int frequency) { Key = key; Frequency = frequency; }

   public string Key { get; set; }

   public int Frequency { get; set; }

}

​