String compression by using repeated characters count

Question

My task was to perform a basic string compression by replacing consecutive repeated characters by one instance of the character and integer denoting the number of repetitions. For example the string "aaaaabbcccdeee" should be reduced to "a5b2c3de3". I have tried working in C# using a simple logic. Please see the below code. Also I have added the condition to not to add the count 1 in the compressed string if there is only single letter occurrence. E.g. if letter "d" is occurred only once in a string "aaabbcccdee" then function will give a compressed string as "a3b2c3de2" and not the "a3b2c3d1e2". To modify this requirement we can change the condition for this single count. Please let me know about the comparative time and space complexity and other efficient way in C#.

class StringCompression
{
    static void Main(string[] args)
    {
        StringCompression sc = new StringCompression();

        sc.CompressionMethod("aaaaabbbccdeeeee");
        sc.CompressionMethod("aaabbccdddee");
        sc.CompressionMethod("a");
    }

    public void CompressionMethod(string originalString)
    {
        List<char> OriginalList = new List<char>();
        List<string> CompressedList = new List<string>();
        OriginalList.AddRange(originalString);
        // Convert to Character Array
        char[] charArray = OriginalList.ToArray();

        int i = 0;
        char character;
        int len = charArray.Length;

        while (i < len)
        {
            int n = 0;
            character = (charArray[i]);
            while (i < charArray.Length && charArray[i] == character)
            {
                n = n + 1;
                i++;
            }

            // add characters to the new list 
            CompressedList.Add(character.ToString());

            // add character counts to the new list 
            if (n == 1)
            {
                // Do nothing
            }
            else
            {
                CompressedList.Add(n.ToString());
            }
        }
        // CompressedList will contain compressed string
        foreach (string str in CompressedList)
        {
            Console.Write(str);
        }
        Console.Write("\n");
        Console.Write("\n");
    }
}

Answer 1

String as an Array

You got your string parameter:

string originalString

Then you turned it into a list:

OriginalList.AddRange(originalString);

Then you turned it into an array:

charArray = OriginalList.ToArray();

And finally used it as:

character = (charArray[i]);

Instead of all that, you could have just done this:

character = (originalString[i]);

Class Design

Instantiating a StringCompression class every time you wanna compress a string can be avoided by just declaring the function CompressionMethod as static since the class has no members anyway. So in Main, you only have to do:

StringCompression.CompressionMethod("String here");

Or better: make it an extension method.

String Builder

Instead of a list of strings in:

CompressedList = new List<string>();

You could instead use a String Builder to create the resulting string.

Answer 2

Single Responsibility Principle

This method is doing to much. It is compressing the string and writes it to the Console. You can avoid this by returning a string from this method and add another method for doing the output.

General

• if you would increase i before the inner while loop you will save one iteration of this loop. You don't need to check the character against itself.
  If you change this you need to initialize n with 1.

• The condition if(n == 1) should be removed because it doesn't add any value. A better way would be to check for n > 1 and if that is true add the count. Here a explaining comment about why this is used would be good.

• speaking about comments, comments should explain why something is done in the way it is done. Let the code speak for itself about what is done by using descriptive names for variables, methods and classes.

  A comment like

  // add characters to the new list 
  CompressedList.Add(character.ToString());  
  

  does not add value to the code but noise. We clearly see that the character is added to the list, so no need to comment on that.

Other than these points I completely agree with @helix answer.

Answer 3

This answer is intended to serve as a compilation of the other two great answers offered here, backed up by example code. Note that the following was tested using the .NET Core 2.2 run-time on a machine with a 64-bit Intel CPU running Ubuntu 19.04 LTS Desktop.

First, the code.

The way I see it, this is the optimal solution for your situation as you have presented it (which as others have helpfully pointed out, is formally referred to as Run-length encoding or RLE):

using System;
using System.Collections.Generic; // Queue
using System.Text; // StringBuilder

namespace ExtensionMethods
{
    public static class Program
    {
        public static void Main(string[] args)
        {
            if (args.Length > 0) {
                foreach (string @string in args) {
                    @string.PrintRLE();
                    @string.PrintRLE(false);
                }
            } else {
                RunLengthEncoding.TestNullOrEmptyRLE();
            }
        }
    }

    public static class RunLengthEncoding
    {
        public static string EncodeRLE(this string inputString, bool postfix = true)
        {
            var buffer = new StringBuilder();

            if (!string.IsNullOrEmpty(inputString)) {
                var queue = new Queue<char>(inputString);
                uint count = 0;

                while (queue.Count > 0) {
                    char character = queue.Dequeue();
                    count++;

                    if (queue.Count == 0 || character != queue.Peek()) {
                        if (postfix) {
                            buffer.Append(character);
                            if (count > 1) buffer.Append(count);
                        } else {
                            if (count > 1) buffer.Append(count);
                            buffer.Append(character);
                        }

                        count = 0;
                    }
                }
            }

            return buffer.ToString();
        }

        public static void PrintRLE(this string inputString, bool postfix = true)
        {
            Console.WriteLine("BEFORE:\t\t{0}\nAFTER:\t\t{1}\nPOSTFIX:\t{2}\n",
                inputString, inputString.EncodeRLE(postfix), postfix);
        }

        public static void TestNullOrEmptyRLE()
        {
            string inputString = null;
            inputString.PrintRLE();
            inputString.PrintRLE(false);
            inputString = "";
            inputString.PrintRLE();
            inputString.PrintRLE(false);
        }
    }
}

Next, the output.

The above code produces the following hard-coded default output:

dyndrilliac@DynHome:~$ dotnet run
BEFORE:     
AFTER:      
POSTFIX:    True

BEFORE:     
AFTER:      
POSTFIX:    False

BEFORE:     
AFTER:      
POSTFIX:    True

BEFORE:     
AFTER:      
POSTFIX:    False

Also you can test custom input on-the-fly from the command-line:

dyndrilliac@DynHome:~$ dotnet run aaaaabbbccdeeeee aaabbccdddee a
BEFORE:     aaaaabbbccdeeeee
AFTER:      a5b3c2de5
POSTFIX:    True

BEFORE:     aaaaabbbccdeeeee
AFTER:      5a3b2cd5e
POSTFIX:    False

BEFORE:     aaabbccdddee
AFTER:      a3b2c2d3e2
POSTFIX:    True

BEFORE:     aaabbccdddee
AFTER:      3a2b2c3d2e
POSTFIX:    False

BEFORE:     a
AFTER:      a
POSTFIX:    True

BEFORE:     a
AFTER:      a
POSTFIX:    False

Finally, the explanation.

1. String as a Queue. We are choosing to transform the input string (which is really just a character array, and more importantly, an implementer of the IEnumerable<char> interface) into a Queue for several reasons. Firstly, while the creation of the Queue is relatively expensive being an O(n) operation, both Peek and Dequeue are O(1) operations. Additionally, it lets us easily process all the characters in the string using simple logic with a single loop cycle which is another O(n) operation. Lastly, a Queue or Stack allows us to easily implement a Pushdown Automaton which can be easily extended to handle lexing/parsing much more complicated string formats than the one dealt with here, and is the type of technique presented in a formal compiler design course at a university.
2. Class design. We're creating a static class that doesn't require instantiation, and also serves as a repository of Extension Methods which are a great feature that allows you to expand the functionality of existing classes (such as System.String) without having to use inheritance and create your own wrapper classes.
3. StringBuilder. As others have suggested, we want to use a StringBuilder. That's because normal strings in .NET are immutable. Every time you think you're changing a string, you're actually creating a whole new string in memory and waiting for garbage collection to take care of de-allocating the old one. Instead of allocating memory for all these string operations, we want to use a StringBuilder which basically provides us with a mutable string for lots of fast cheap concatenation operations.
4. Single Responsibility Principle. We have chosen to implement three separate methods each with a singular purpose: one to encode a string, another to print that encoding to standard output, and finally a special-case test driver to print the output for two hard-coded strings (empty string and null pointer). This allows us to modify the algorithm logic without affecting the input/output logic and vice-versa.
5. General Loop Optimizations. This code attempts to achieve the goal of the original while minimizing the number of loop iterations and minimizing the number of operations per loop iteration.
6. Descriptive Variable Names. Note that we used descriptive variable names to make it relatively easy to follow the algorithm. No single character variable names like i or s.
7. Optional Postfix Parameter. Lastly, by adding an optional bool parameter to the argument lists of both methods, we can choose whether we want the resulting encoded string to be postfix (count comes after character) or prefix (count comes before character). We shouldn't duplicate code unnecessarily; making two encoding methods and two print methods to accommodate a postfix/prefix choice would be wasteful.

More about the choice to use a Queue

While it would be faster in this case to use the array directly, that's only due to the upfront cost of copying the data from the array into the queue. One of the upsides of the queue is similar to the rationale for the StringBuilder in that the queue provides mutability (unlike an array/string) thanks to Dequeue, which as previously mentioned is an O(1) operation! This also allows the code to more easily be adapted for more complicated context-free parsing algorithms that depend on the behavior of a queue or stack to implement a Pushdown Automaton, like the LL parser. To be clear, it's not that you can't implement a Pushdown Automaton with an array (it's not uncommon for Queues and Stacks to be backed up under-the-hood by ArrayList objects or similar, after all) - but all the additional loops and code that would require make it unnecessarily harder to read the solution. In the case of more complex algorithms, clean code that's easy to read is more valuable than the one-time upfront cost of calling the queue constructor. This answer assumes that the person asking this question will eventually need to perform more complex translation operations in the future, and the formal techniques and algorithms that use more robust data structures tend to be easier to scale-up than those that don't. Another nice thing about going the Pushdown Automaton route is that if you start out writing a bottom-up parser with a stack (where the top of the stack represents the last successfully read token) and then decide part-way through that it would be better to do a top-down parser with a queue (where the front of the queue represents the first successfully read token), then you can keep most or all of the logic the same and just simply Find/Replace Dequeue with Pop and Enqueue with Push or vice-versa. Peek remains Peek whether you are peeking at the front of a queue or the top of a stack.

Answer 4

Apart from other reviews I show you an alternative how you can make this really short with LINQ and Regex:

OK, the first solution wasn't perfect. This one will however do it correctly:

var alphabet = Enumerable.Range(97, 26).Select (i => (char)i + "+");
var pattern = "(" + string.Join("|", alphabet) + ")";

var compressed2 =
    Regex.Matches(str, pattern)
    .Cast<Match>().Select (m => new 
    { 
        Char = m.Groups[1].Value[0], 
        Count = m.Groups[1].Value.Length 
    })
    .Aggregate (string.Empty, (result, nextGroup)  => 
        result.ToString() 
        + nextGroup.Char 
        + (nextGroup.Count > 1 ? nextGroup.Count.ToString() : string.Empty));

For:

var str = "aaabbccdddeezbbb";

the result is:

a3b2c2d3e2zb3

• First get letter groups with regex and their lengths
• Then aggregate them to the final string