TypeScript Coding Challenge #2 – String Compression

Our task today is to write a function for String compression in TypeScript.

Implement a method that replaces repeated characters by the character and a number indicating how often the character occurs in a single repetition. To give you one example: aabcccccaaa should be compressed to a2b1c5a3. If the compressed string would not become smaller than the original one, we should return the original string. A string has only uppercase and lowercase letters (a-z).

Setup

We’re again using a custom “test function” as in our previous post about all unique characters. This time we just rename it to “assert”, change the order of the parameters and add some generics to ensure we’re working with the correct types:

function assert<I, O>(input: I, fn: (value: I) => O, expectedValue: O) {
    const result = fn(input);
    const assertionString = result === expectedValue ? '\u2713' : `\u2717 expected ${expectedValue}`;
    const color = result === expectedValue ? '\x1b[32m' : '\x1b[31m';
    console.log(color, `'${input}' => ${result} ${assertionString}`, '\x1b[0m');
}

The ‘\u2713’, etc. will ensure our output is either appearing in green or red depending on the success or failure of comparing the actual output (result) with the expectedValue. Check out this post to learn about colouring your Node JS terminal output.

Solution

We define a function that accepts a string input. First, we take care of an edge case and return the input if the string length is smaller than 3. For example the input aa with length 2 would be compressed to a2 which is unnecessary.
Now let’s take care of the remaining cases. In a for loop consecutive characters are compared and the repetitionCount is increased if the characters following each other are the same. As soon as the characters stop repeating themselves we can add the character alongside the repetitionCount to the output. At the same time we should reset the repetitionCount to the initial value of 0.
Finally we check whether the compression did really help and only return the compressed variant if it’s shorter.

function compressString(input: string): string {
    if (input.length < 3) {
        return input;
    }

    let output = '';
    let repetitionCount = 0;
    for (let i = 0; i < input.length; i++) {
        repetitionCount++;
        if (input[i] !== input[i+1]) {
            output += `${input[i]}${repetitionCount}`;
            repetitionCount = 0;
        }
    }
    return output.length < input.length ? output : input;
}

Let’s run this with a few examples:

assert('test', compressString, 'test');
assert('aabcccccaaa', compressString, 'a2b1c5a3');
assert('ttuuuz', compressString, 'ttuuuz');
assert('eeeee', compressString, 'e5');
assert('a', compressString, 'a');
assert('aa', compressString, 'aa');
assert('aaa', compressString, 'a3');
assert('', compressString, '');

This shows us the following in our console:

The first string ‘test’ is not worth compressing as it would end up being ‘t1e1s1t1’ which is not shorter than ‘test’ itself. We can get rid of a bit of string length for the second example though: ‘aabcccccaaa’ ends up as ‘a2b1c5a3’.