TypeScript Coding Challenge #1 – All Unique Characters

In this post we want to implement a TypeScript algorithm that tells us if a string contains all unique characters:

Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?

We’re going to split this into two parts. First, we start with the simple variant where we are able to use additional data structures and in the second part we can make it more difficult.

But first let’s quickly setup some code to help us test our solutions later.

Setup

As a first step we define the interface for the function that implements our solution:

fn: (value: string) => boolean

Hence, we are setting up the following testFunction to pass the input string, alongside the expected value and the function that implements our solution.

function testFunction(input: string, expectedValue: boolean, fn: (value: string) => boolean) {
    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}`);
}

Solution with additional data structures

We know that in JavaScript the Set object lets you store unique values of any type, whether primitive values or object references. We can use this characteristic to solve our problem:

function hasAllUniqueCharacters(input: string): boolean {
    const characterSet = new Set(input.split(''));
    return input.length === characterSet.size;
}

We test this solution by calling our testFunction defined above:

console.log('-----------------------------------');
testFunction('test', false, hasAllUniqueCharacters);
testFunction('abc', true, hasAllUniqueCharacters);
testFunction('all', false, hasAllUniqueCharacters);
testFunction('', true, hasAllUniqueCharacters);

And in our console we can see as a result:

Everything is fine. Let’s move on to the second part of the task and tackle the variant without using any additional data structures.

Solution without additional data structures

For this solution we have to loop through the characters and compare them with each other. If we then find two identical characters and their indices are not equal (i.e. not the same character in the input) we can return false.

function hasAllUniqueCharactersV2(input: string): boolean {
    for (let i = 0; i < input.length; i++) {
        for (let j = 0; j < input.length; j++) {
            if (input[i] === input[j] && i !== j) {
                return false;
            }
        }
    }

    return true;
}

This algorithm has a time complexity of O(n²). One alternative would be to sort the input string’s characters and compare neighbouring characters. This would bring down the time complexity to O(n log n).

Anyway, testing this second function (hasAllUniqueCharactersV2) works analog to the previous one. We just pass the function as third parameter:

testFunction('test', false, hasAllUniqueCharactersV2);
// etc.

This gives us the following output in the console:

Problem solved! We have shown two possible implementations in TypeScript to determine if a string contains all unique characters.

Note: Why didn’t I use a test framework? Because for now I prefer the 4 lines of testFunction. No need to install and setup some 3rd party code.