Global Nerdy

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)) {
            uniqs.add(ch);
        } else {
            repeats.add(ch);
        }
    }
    
    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(n²). So the whole function is O(n²).

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.

Previously in this series

• How to solve coding interview questions: The first NON-recurring character in a string
• Coding interview questions: “First recurring character” in Swift
• How to solve coding interview questions: The first recurring character in a string
• I Has the Dumb (or: How I Embarrassed Myself in My Interview with Google) — from way back in 2013

Welcome back to How to solve coding interview questions! In this series of articles, I’ll walk you through the sort of questions that you might be asked in a coding interview and provide solutions in a couple of programming languages.

In the previous article in this series, I presented you with a challenge to write a function that took a string as an argument and returned either:

• The first recurring character in the given string, if one exists, or
• A null value like JavaScript’s or Kotlin’s null, Python’s None, or Swift’s nil.

I also provided solutions in Python, JavaScript, and Swift.

The follow-up challenge

Usually in a coding interview, if you succeed at the initial challenge, there’s usually a follow-up that is a more challenging variation on the theme. The “find the first recurring character” challenge is often followed up by looking for its opposite:

Write a Python function named first_nonrecurring_character() or a JavaScript function named firstNonRecurringCharacter() that takes a string and returns either:

• The first NON-recurring character in the given string, if one exists, or
• A null value like JavaScript’s or Kotlin’s null, Python’s None, or Swift’s nil.

Here are some example inputs for the function, along with what their corresponding outputs should be:

If you give the function this input…	…it should produce this output:
'aabbbXccdd'	'X'
'a🤣abbbXcc3dd'	'🤣'
‘aabbccdd'	null / None / nil

One solution

See if you can code it yourself, then scroll down for my solution.

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

Let’s consider the following example string:

"a🤣abbbXcc3dd"

The string is short, and I purposely made the first non-recurring character an emoji so that it would be easy to spot, so a glance is all you need to spot it.

One programmatic approach is to go through the string one character at a time and keep track of the number of times you’d encountered each character. For this example string, you’d end up with this:

Character	Number of times it appeared in the string
a	2
🤣	1
b	3
X	1
c	2
3	1
d	2

If you maintain the order in which the characters were encountered, the solution becomes either:

• The first character that appears 1 time in the string, if one exists, or
• A null value like JavaScript’s or Kotlin’s null, Python’s None, or Swift’s nil.

This was my first pass at a solution in Python:

# 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
            
    # Now that we have a record of the number of times each character appears,
    # create a list containing only those characters that have appeared once.
    non_recurring_character_record = {k:v for (k, v) in character_record.items() if v == 1}
    non_recurring_characters = list(non_recurring_character_record.keys())
    
    # The first non-recurring character, if there is one,
    # is the first item in the list of non-recurring characters.
    if len(non_recurring_characters) == 0:
        return None
    else:
        return non_recurring_characters[0]

What’s the Big O?

In the code above, there are 2 O(n) operations:

• The for loop that builds a record of the number of times each character appears in the text, and
• This list comprehension:

# Python

{k:v for (k, v) in character_record.items() if v == 1}

These operations take place one at a time, so the complexity of the code is O(2n). As far as computational complexity is concerned, constants don’t really matter; O(2n) is effectively the same as O(n). So its computational complexity is O(n).

An (unsuccessful) attempt to make the solution a little more time- and space-efficient

In its current form, the code builds a record of the number of times each character appears in the text — even those that appear more than once. Then, in the next step, it goes through that record to create a new record of the characters that appear only once.

I thought: “What if we eliminated that second step by building a record of only characters that appeared once?”

Here’s pseudocode that explains what I mean:

For each character in the text:
    If the current character is already in the record:
        Remove that character from the record
    Otherwise:
        Add that character to the record

At the end of the for loop, the character record contains only the characters that have appeared once.

Here’s my revised implementation:

# Python

def first_non_recurring_character(text):
    character_record = {}
    
    # Go through the text one character at a time
    # but record ONLY those characters that appear once.
    # 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:
            # We've seen this character before,
            # so remove it from the record.
            del character_record[character]
        else:
            # # We've never seen this character before,
            # so add it to the record.
            character_record[character] = 1        
    
    # character_record contains only those characters
    # that appear ONCE in the string
    non_recurring_characters = list(character_record.keys())
    
    if len(non_recurring_characters) == 0:
        return None
    else:
        return non_recurring_characters[0]

This solution seems like a good idea, but it has a big flaw! As one reader, Hans, astutely pointed out in a comment:

basically it tests if characters appear an odd number of times in a string. For example if a character appears a third time, it was removed the second time and consequently added again to character_record that third time.

This is true — by removing a character from character_record, it’s as if the character was never encountered. I’m going to treat this as a reminder to:

• Not prematurely discard information, and
• Write better tests!

So in the end, I should stick with my first solution. Good catch, Hans, and thanks for pointing out my mistake!

Previously in this series

• Coding interview questions: “First recurring character” in Swift
• How to solve coding interview questions: The first recurring character in a string
• I Has the Dumb (or: How I Embarrassed Myself in My Interview with Google) — from way back in 2013