using System;

using System.Collections.Generic;

​

/*

ASSUMPTIONS

-- From the example given , there are two substrings with length of 3 (fab and abc). 

        Since it is expected that abc is chosen, I have it set so that ties are broken by choosing the string that appears (for the first time) the latest.

-- Capital letters are not the same as lowercase letters.

-- Expect the string to be comprised of keyboard characters.

*/      

​

/*

TIME COMPLEXITY : O(n)

    Each for loop iterates 'n' times.

SPACE COMPLEXITY: O(n)

    The dictionary grows linearly as 'n' grows.

*/  

​

public class Program

{

    public static void Main()

    {

        // Expected: [, 0]

        var values1 = fiddle("this098is9823afiddle", 123456789);

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

        // Expected [, 1]

        var values2 = fiddle("", 0);

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

        // Expected [, 0]

        var values3 = fiddle("", 5);

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

        // Expected [, 12]

        var values4 = fiddle("thisISaTEST", 0);

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

        // Expected [test, 5]

        var values5 = fiddle("test[-testp-test]0--test0i[-test-hello,mountain", 4);

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

        // Expected [an, 1]

        var values6 = fiddle("MyNameIsHerman", 2);

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

        // Expected [w, 4]

        var values7 = fiddle("wowww-']C#[Compiles><)Very][]:Quick", 1);

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

        // Expected [case, 2]

        var values8 = fiddle("LET_ US    TEST capitals vs lower casecase TeST test", 4);

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

        // Expected: [abc, 2]

        var values9 = fiddle("zfabcde224lkfabc51+crsdtab=", 3);

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

    }

    public static KeyValuePair<string,int> fiddle(string st, int len)

    {

        // Use this to store substrings of length 'len' and to count their occurances

        Dictionary<string, int> subStrs = new Dictionary<string, int>();

        string temp = "";

        string maxKey = "";

        int maxVal = 0;

        // Iterate over the input string and populate the dictionary

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

        {

            temp = st.Substring(i, len);

            // If the current substring is in the dictionary

            // then increment the value

            if (subStrs.ContainsKey(temp)) 

                subStrs[temp] += 1;

            // If the current substring isn't in the dictionary

            // then add it to the dictionary

            else 

                subStrs.Add(temp, 1);

        }

        // Iterate over the dictionary to choose the substring that has been seen the most

        // break ties by choosing the string that is most recently added to the dictionary.

        foreach (var key in subStrs.Keys)

        {

            if (subStrs[key] >= maxVal ) 

            {

                maxKey = key;

                maxVal = subStrs[key];

            }

        }

        return new KeyValuePair<string,int>(maxKey, maxVal);

    }

}

​

​