using System;

using System.Collections; 

using System.Collections.Generic;

using System.Linq;

using System.Diagnostics; 

​

public class Program

{

    public static void Main()

    {

​

        List<char> left = new List<char>() { '7', '1', '2', '3', '4', '5', '9', '7','7','1' }; //{ 'a', 'a', 'a', 'a', 'b', 'b', 'c' };

        List<char> right = new List<char>() {'1', '1', '2', '2', '3', '4', '5', '5', '5','5','5' };  //{ 'a', 'a', 'b', 'c' };

        Stopwatch watch = new Stopwatch();

​

        watch.Start();

​

        // Hash solution

        var counts = right

          .GroupBy(item => item)

          .ToDictionary(chunk => chunk.Key, chunk => chunk.Count());

​

        var result = left

          .GroupBy(item => item)

          .SelectMany(chunk => chunk.Skip(counts.TryGetValue(chunk.Key, out var skip) ? skip : 0))

          .ToList();

​

        watch.Stop();

​

        TimeSpan tHash = watch.Elapsed;

​

        Console.WriteLine("Output: " + string.Join(",", result) + " in " + watch.ElapsedTicks + " ticks.");

        watch.Reset();

        watch.Start();

​

        // Initial solution

        var difference = left.ToList();

​

        foreach (var entry in right) {

          difference.Remove(entry);

        }

        watch.Stop();

​

        TimeSpan tInitial = watch.Elapsed;

        Console.WriteLine("Output: " + string.Join(",", difference) + " in " + watch.ElapsedTicks + " ticks.");

​

        Console.Write($"Hash: {tHash}; Initial {tInitial}");

        left = new List<char>() { '7', '1', '2', '3', '4', '5', '9', '7','7','1' }; //{ 'a', 'a', 'a', 'a', 'b', 'b', 'c' };

        right = new List<char>() {'1', '1', '2', '2', '3', '4', '5', '5', '5','5','5' };  //{ 'a', 'a', 'b', 'c' };

        watch.Reset();

        watch.Start();

        right.ForEach(item => left.Remove(item));

​

        watch.Stop();

​

        Console.WriteLine("Output: " + string.Join(",", right) + " in " + watch.ElapsedTicks + " ticks.");

        //list1: { "a", "b" }

    }

}