using System;

using System.Collections.Generic;

using System.Text;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Running task 2 version 1");

        foreach(var data in SampleData())

        {

            var expectedResult = (int) data[2];

            var result = Solution(data[0].ToString(), (int) data[1]);

            Assert.Equal(expectedResult, result);

        }

        Console.WriteLine("All tests passed!");

    }

    /*

     * Brute force solution: we find all the compressed versions of the string

     * and return the length of the shortest one.

     * 

     * The solution is straightforward and easy to understand, but the price

     * we pay is the time and space complexity of O(n^2)

     */

    public static int Solution(string s, int k)

    {

        var strLen = s.Length;

        if (strLen <= k)

        {

            return 0;

        }

        if (strLen - k == 1)

        {

            return 1;

        }

​

        var shortest = int.MaxValue;

        var i = 0;

        while (i + k - 1 < strLen)

        {

            var str = s.Remove(i, k);

            var compressed = Compress(str);

            if (shortest > compressed.Length)

            {

                shortest = compressed.Length;

            }

            i++;

        }

​

        return shortest;

    }

​

    private static string Compress(string s)

    {

        var sb = new StringBuilder();

        var curChar = s[0];

        var count = 0;

        foreach (var c in s)

        {

            if (c == curChar)

            {

                count++;

            }

            else

            {

                AppendContent(sb, curChar, count);

                curChar = c;

                count = 1;

            }

        }

​

        AppendContent(sb, curChar, count);

​

        return sb.ToString();

    }

​

    private static void AppendContent(StringBuilder sb, char curChar, int count)

    {

        if (count == 1)

        {

            sb.Append(curChar);

        }

        else

        {

            sb.Append(count).Append(curChar);

        }

    }

    public static IEnumerable<object[]> SampleData()

    {

        yield return new object[] { "abbbccddccc", 3, 5 };

        yield return new object[] { "aaaaaaaaaaabbxaaaaaaaaaa", 3, 3 };

        yield return new object[] { "aaaaaaaaaaaaaaaaaaaaa", 3, 3 };

        yield return new object[] { "aaaaaaaaaa", 3, 2 };

        yield return new object[] { "aaaaaaaaaaabbxaaaaaaaaaa", 0, 9 };

        yield return new object[] { "abcdddefg", 2, 6 };

        yield return new object[] { "a", 2, 0 };

        yield return new object[] { "aab", 3, 0 };

        yield return new object[] { "aab", 0, 3 };

        yield return new object[] { "abadagggff", 9, 1 };

        yield return new object[] { "abcdsgf", 3, 4 };

        yield return new object[] { "baaacdsagf", 3, 5 };

        yield return new object[] { "bacdsaaagf", 3, 5 };

    }

    public static class Assert

    {

        public static void Equal(int expected, int actual)

        {

            if (expected != actual)

            {

                var message = "Assert.Equal() Failure\n"

                    + "Expected: " + expected + "\n"

                    + "Actual: " + actual;

                throw new Exception(message);

            }

        }

    }

}

​

​