using System.Text;

using System;

public class Program

{

    public static void Main()

    {

        Console.WriteLine(CompressStringNaiveApproach("Straightforward:"));

        Console.WriteLine(CompressStringNaiveApproach("aaabccccdd"));

        Console.WriteLine(CompressStringNaiveApproach("yyyyyzzzzzzzzzz"));

        Console.WriteLine(CompressStringNaiveApproach("abcd"));

        Console.WriteLine(CompressStringNaiveApproach("hhhccchhhccc"));

        Console.WriteLine("\n");

        Console.WriteLine(CompressStringNaiveApproach("Optimize space complexity:"));

        Console.WriteLine(CompressStringOptimizeSpaceComplexity(new StringBuilder("aaabccccdd")));

        Console.WriteLine(CompressStringOptimizeSpaceComplexity(new StringBuilder("yyyyyzzzzzzzzzz")));

        Console.WriteLine(CompressStringOptimizeSpaceComplexity(new StringBuilder("abcd")));

        Console.WriteLine(CompressStringOptimizeSpaceComplexity(new StringBuilder("hhhccchhhccc")));

    }

     /*  straightforward / naive approach:

         *  Space complexity O(n)

         *  Time  complexity O(n) 

        */

        private static string CompressStringNaiveApproach(string originalString)

        {

             if (string.IsNullOrEmpty(originalString) || originalString.Length == 1)

                return originalString;

​

            var resultBuilder = new StringBuilder(originalString.Length);

            var currentCharFrequency = 1;

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

            {

                if( i>0 && originalString[i] == originalString[i-1])

                {

                    currentCharFrequency++;

                    if(i == originalString.Length-1)

                    {

                        resultBuilder.Append(currentCharFrequency);

                    }

                }

                else

                {

                    if (currentCharFrequency > 1)

                    {

                        resultBuilder.Append(currentCharFrequency);

                        currentCharFrequency = 1;

                    }

                    resultBuilder.Append(originalString[i]);

                }    

            }

            return resultBuilder.ToString();

​

        }

​

​

         // if the function recieves the text as string then since string is immutable we can't do in place changes.

        // If the function will recieve the text as StringBuilder then we can reduce the space complexity to O(1) using following logic.

        private static string CompressStringOptimizeSpaceComplexity(StringBuilder originalString)

        {

             if (originalString == null)

                return null;

            if (originalString.Length < 2)

                return originalString.ToString();

​

​

            var slow = 0;

            var fast = 1;

            var last=0; // this will represent the  index of last character of comressed text inside the original string

​

            while (fast <= originalString.Length)

            {

                if (fast != originalString.Length && originalString[fast] == originalString[slow])

                {

                    fast++; // we will increment only the fast index if repeating characters

                }

                else

                {

​

                    int repeatCount = fast - slow;

                    originalString[last++] = originalString[slow];

                    if (repeatCount > 1)

                    {

                        var repeatCountChars = repeatCount.ToString().ToCharArray();

                        foreach (char c in repeatCountChars)

                        {

                            originalString[last] = c;

                            last++;

                        }

​

​

                    }

                    slow = fast++;

​

                }

​

            }

            return originalString.Remove(last, originalString.Length-last).ToString();

​

        }

}