A few weeks ago I subscribed to Cassidy's newsletter. I have been struggling with my constantly overflowing email accounts for a couple of years now. Thus, I'm a bit picky with what I sign up for. This one is different! I love the format. I love that it is to the point whilst delivering an interesting selection of reading every week. It's witty, it's funny and it's interesting. Give it a try: have a rendezvous with cassidoo!
Task description
In each of her newsletters, Cassidy publishes an Interview Question of the week. A short code quiz for developers.
Write a function that determines if all the characters in a given string are unique. Can you do this without making any new variables? You choose if you want to include capitalization in your consideration for this one, as a fun challenge.
Example:allUnique('Cassidy') // false allUnique('cat & dog') // false allUnique('cat+dog') // false— Cassidy's newsletter, the 30th of May , 2022
TL;DR
I get it, life's too short. Here are my three ways of solving the quiz:
Tests
I'll be honest. I'm still getting my head around writing tests first. This is an easy quiz with clearly defined conditions. I took it on the chin and wrote my tests first like the good boy I am! Woof! Originally, I was just going to do one solution for the quiz. As I managed to do so pretty fast, I decided to roll out a few other ways to solve the quiz. This is when I found the tests extremely handy. I didn't have to check whether my other solutions worked on not. I knew it straight away when the tests passed.
import { allUnique } from "./index";
describe("Strings of unique characters", () => {
it("should return `false` if there are present the same characters in the string", () => {
expect(allUnique("Cassidy")).toBe(false);
expect(allUnique("cat & dog")).toBe(false);
expect(allUnique("crs1138")).toBe(false);
});
it("should return `true` if no character is repeated", () => {
expect(allUnique("cat+dog")).toBe(true);
expect(allUnique("abcdefghijklmnopqrstuvwxyzA")).toBe(true);
expect(allUnique("abcdefghijklmnopqrstuvwxyz 1234567890")).toBe(true);
});
});
Solution 1 – the Array.prototype.reduce()
My primary weapon of choice was ES6 and its higher-order function reduce(). I split the string into individual characters in an array. In the callback function, I check if that character was already present in the array. If not, I added it to the acc accumulator. In the end, I compare the length of the original string and the length of the array with unique characters to decide whether to return true or false.
I use arr.splice(1) to break out from the reduce callback loop when a duplicate character has been found. arr.splice(1) mutates the original array the reduce was launched on. The mutated array has only one item and therefore the callback loop is stopped. In this case I don't mind the mutation of the array as it is only to point out a repeated character.
function allUnique(str) {
const chars = str.split("").reduce((acc, next, i, arr) => {
if (acc.includes(next)) {
arr.splice(1); //break out of reduce early
}
return !acc.includes(next) ? (acc = acc + next) : acc;
}, "");
return str.length === chars.length;
}
I noticed that I'm checking twice for the presence of the next character – acc.includes(next)). A little refactor and tadaaa – here is my first result with the callback on one line:
export function allUnique(str) {
const chars = str.split("").reduce((acc, next, i, arr) => {
return acc.includes(next) ? arr.splice(1) && acc : (acc = acc + next);
}, "");
return str.length === chars.length;
}
Solution 2 – the while() loop
Another solution that sprung up to my mind is the classic ES5 way. Just use the while() loop, Luke!
The algorithm is pretty straight forward. Break the string into an array of individual characters. Declare an empty array for uniques and loop over all the characters. If the char is unique add it to the uniques array. If it finds a repeated character return false, otherwise after going through all of them return true.
function allUnique(str) {
const chars = str.split("");
let uniques = [];
while (chars.length > 0) {
const letter = chars.pop();
if (uniques.indexOf(letter) >= 0) {
return false;
}
uniques.push(letter);
}
return true;
}
I have not used the Array.prototype.indexOf() in donkey's years. It seems a bit archaic in comparison with the Array.prototype.includes(). There was no extra challenge in this solution.
Solution 3 – the String.prototype[@@iterator]()
It occurred to me that I could learn/practice something I don't do everyday. I went for the String.prototype[@@iterator]() method.
function allUnique(str) {
const iterator = str[Symbol.iterator]();
let char = iterator.next();
let uniques = "";
while (!char.done) {
if (uniques.includes(char.value)) {
break;
}
uniques = uniques + char.value;
char = iterator.next();
}
return str.length === uniques.length;
}
First of all I create an iterator object const iterator = str[Symbol.iterator](). This object has one method iterator.next(). When called it returns the next character in the str string.
I call let char = iterator.next() for the first time declaring the character object. The object has two properties: char.value containing the value of the currently iterated character and a boolean char.done signalling whether there is another character for the iterator to go to if I was to call iterator.next() again.
I prepare my string for unique characters – uniques and start looping over checking for the current character value being already present in the string of unique characters. If that happens I break out of the loop. Otherwise, I add the character to the uniques and move on to the next one.
After the loop has finished one way or another I compare the lengths of the original string with the collected unique characters and return true if they are equal or false when they are not.
The specs for the String.prototype[@@iterator]() method are worth reading as this is a rarely used concept for many devs, myself included.
And the winner is…
So, I've got three solutions but which one is truly the best? As the truth is in the eye of the beholder, thus it depends on the definition of best. Some might argue that the first solution (reduce()) is the shortest, others could say the second solution (while()) is the easiest to read, whilst another group could vouch for the third solution being the most modern (whatever that might mean).
I decided to compare the performance of each solution. There are various benchmark tools to measure JS performance available online. I tried three that came up on my Google search results. They all have similar UI, letting me put all three solutions next to each other. I defined a bunch of shorter and longer strings, including two with all of the basic keyboard characters (one with and the other one without repetition). When I launched the test it runs each solution extensively and measure how many operations per second it was able to execute. The bigger number the better as it means fewer resources are needed to run the solution.
Results
The worst performance out of the three solutions had in all tests the while() solution. Its performance was on average around 60% lower than the most performant solution. The second-best performing solution was the reduce() function, being on average around 13% lower than the fastest solution.
And the winner is, drum roll… The iterator solution!
It needs to be said that the iterator solution started to outperform the other two once the break-out condition was added to the equation. Before that, it had surprisingly poor results. My conclusion is that the iterator is worth learning but I shall run performance tests for individual use cases.
Cover image Shoe Paisley by Emma Plunkett
Top comments (0)