Categories

# How to solve coding interview questions: Looking deeper into finding the first NON-recurring character in a string

In the previous installment in the How to solve coding interview questions series, I showed you my Python solution for the challenge “Find the first NON-recurring character in a string,” which is a follow-up to the challenge “Find the first recurring character in a string.”

A couple of readers posted their solution in the comments, and I decided to take a closer look at them. I also decided to write my own JavaScript solution, which led me to refine my Python solution.

## “CK”’s JavaScript solution

The first reader-submitted solution comes from “CK,” who submitted a JavaScript solution that uses sets:

``````// JavaScript

function findFirstNonRepeatingChar(chars) {
let uniqs = new Set();
let repeats = new Set();

for (let ch of chars) {
if (! uniqs.has(ch)) {
} else {
}
}

for (let ch of uniqs) {
if (! repeats.has(ch)) {
return ch;
}
}

return null;
}``````

The one thing that all programming languages that implement a set data structure is that every element in a set must be unique — you can’t put more than one of a specific element inside a set. If you try to add an element to a set that already contains that element, the set will simply ignore the addition.

In mathematics, the order of elements inside a set doesn’t matter. When it comes to programming languages, it varies — JavaScript preserves insertion order (that is, the order of items in a set is the same as the order in which they were added to the set) while Python doesn’t.

CK’s solution uses two sets: `uniqs` and `repeats`. It steps through the input string character by character and does the following:

• If `uniqs` does not contain the current character, it means that we haven’t seen it before. Add the current character to `uniqs`, the set of characters that might be unique.
• If `uniqs` contains the current character, it means that we’ve seen it before. Add the current character to `repeats`, the set of repeated characters.

Once the function has completed the above, it steps through `uniqs` character by character, looking for the first character in `uniqs` that isn’t in `repeats`.

For a string of length n, the function performs the first `for` loop n times, and the second `for` loop some fraction of n times. So its computational complexity is O(n).

Thanks for the submission, CK!

## Dan Budiac’s TypeScript solution

Dan Budiac provided the second submission, which he implemented in TypeScript:

``````// TypeScript

function firstNonRecurringCharacter(val: string): string | null {

// First, we split up the string into an
// array of individual characters.
const all = val.split('');

// Next, we de-dup the array so we’re not
// doing redundant work.
const unique = [...new Set(all)];

// Lastly, we return the first character in
// the array which occurs only once.
return unique.find((a) => {
const occurrences = all.filter((b) => a === b);
return occurrences.length === 1;
}) ?? null;

}``````

I really need to take up TypeScript, by the way.

Anyhow, Dan’s approach is similar to CK’s, except that it uses one set instead of two:

1. It creates an array, `all`, by splitting the input string into an array made up of its individual characters.
2. It then creates a set, `unique`, using the contents of `all`. Remember that sets ignore the addition of elements that they already contain, meaning that `unique` will contain only individual instances of the characters from `all`.
3. It then goes character by character through `unique`, checking the number of times each character appears in `all`.

For a string of length n:

• Splitting the input string into the array `all` is O(n).
• Creating the set `unique` from `all` is O(n).
• The last part of the function features a find() method — O(n) — containing a filter() method — also O(n). That makes this operation O(n2). So the whole function is O(n2).

Thanks for writing in, Dan!

## My JavaScript solution that doesn’t use sets

In the meantime, I’d been working on a JavaScript solution. I decided to play it safe and use JavaScript’s `Map` object, which holds key-value pairs and remembers the order in which they were inserted — in short, it’s like Python’s dictionaries, but with `get()` and `set()` syntax.

``````// JavaScript

function firstNonRecurringCharacter(text) {
// Maps preserve insertion order.
let characterRecord = new Map()

// This is pretty much the same as the first
// for loop in the Python version.
for (const character of text) {
if (characterRecord.has(character)) {
newCount = characterRecord.get(character) + 1
characterRecord.set(character, newCount)
} else {
characterRecord.set(character, 1)
}
}

// Just go through characterRecord item by item
// and return the first key-value pair
// for which the value of count is 1.
for (const [character, count] of characterRecord.entries()) {
if (count == 1) {
return character
}
}

return null
}``````

The final part of this function takes an approach that’s slightly different from the one in my original Python solution. It simply goes through `characterRecord` one key-value pair at a time and returns the key for the first pair it encounters whose value is 1.

It remains an O(n) solution.

## My revised Python solution

If I revise my original Python solution to use the algorithm from my JavaScript solution, it becomes this:

``````# Python

def first_non_recurring_character(text):
character_record = {}

# Go through the text one character at a time
# keeping track of the number of times
# each character appears.
# In Python 3.7 and later, the order of items
# in a dictionary is the order in which they were added.
for character in text:
if character in character_record:
character_record[character] += 1
else:
character_record[character] = 1

# The first non-recurring character, if there is one,
# is the first item in the list of non-recurring characters.
for character in character_record:
if character_record[character] == 1:
return character

return None``````

This is also an O(n) solution.

## 3 replies on “How to solve coding interview questions: Looking deeper into finding the first NON-recurring character in a string”

[…] previous posts, I’ve presented Python, JavaScript, and TypeScript solutions for the coding interview challenge: […]

[…] How to solve coding interview questions: Looking deeper into finding the first NON-recurring charact… […]

[…] How to solve coding interview questions: Looking deeper into finding the first NON-recurring charact… […]