using System;

using System.Collections.Generic;

using System.Linq;

using System.Diagnostics;

public class Program

{

    public static void Main()

    {

        var testData = "ABCBAD";

        var s1 = Stopwatch.StartNew();

        Console.WriteLine(firstRepeating(testData));

        s1.Stop();

        Console.WriteLine("HashSet ====> " + ((double)(s1.Elapsed.TotalMilliseconds * 1000000) /testData.Count()).ToString("0.00 ns"));

        /*

        var s2 = Stopwatch.StartNew();

        Console.WriteLine(FirstRepeatingLetter(testData));

        s2.Stop();

        Console.WriteLine("Dictionary ====> " + ((double)(s2.Elapsed.TotalMilliseconds * 1000000) /testData.Count()).ToString("0.00 ns"));

        var s3 = Stopwatch.StartNew();

        Console.WriteLine(FirstRepeatingLetter1(testData));

        s3.Stop();

        Console.WriteLine("Dictionary ====> " + ((double)(s3.Elapsed.TotalMilliseconds * 1000000) /testData.Count()).ToString("0.00 ns"));

        */

    }

    // This function prints the first Time complexity: O(N)

    public static char firstRepeating(string str) 

    { 

        // Creates an empty hashset 

        HashSet<char> h = new HashSet<char>();

        char[] charArray = str.ToCharArray();

        // Traverse the input array 

        // from left to right 

        for (int i = 0; i <= charArray.Length - 1; i++) 

        { 

            char c = charArray[i];

            // If element is already in hash set, 

            // update x and then break 

            if (h.Contains(c)) 

            { 

                return c; 

            }

​

            else // Else add element to hash set 

            { 

                h.Add(c); 

            } 

        }

        return '\0';

    }

    // Time complexity: O(N)

    public static char FirstRepeatingLetter(string str)

    {

            Dictionary<char, int> charFrequencyDic = new Dictionary<char, int>();

            char[] charArray = str.ToCharArray();

            for (int i = 0; i < charArray.Length; i++)

            {

                if(!charFrequencyDic.ContainsKey(charArray[i]))

                    charFrequencyDic.Add(charArray[i],1);

                else

                    charFrequencyDic[charArray[i]]+=1;

            }

            var query = charFrequencyDic.Where(r => r.Value > 1).Select(r => r.Key);

            if (query.Any())

                return query.First();

            else

                return new Char();

        }

    // Time complexity: O(N^2)

    public static char FirstRepeatingLetter1(string str)

    {

            char[] charArray = str.ToCharArray();

            for (int i = 0; i < charArray.Length; i++)

            {

                int j = i + 1;

                if (str.Substring(j).Contains(charArray[i].ToString()))

                    return charArray[i];

            }

            return new Char();

      }

}