Global Nerdy

In previous posts, I’ve presented Python, JavaScript, and TypeScript solutions for the coding interview challenge: “Write a function that returns the first NON-recurring character in a given string.” In this post, I’ll show you my solution in Swift.

Here’s a table that provides some sample input and corresponding expected output for this function:

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

The algorithm

I’ve been using an algorithm that takes on the problem in two stages:

In the first stage, the function steps through the input string one character at a time, counting the number of times each character in the string appears in a “character record”. Because we’re looking for the first non-recurring character in the input string, the order in which data is stored in the character record is important. It needs to maintain insertion order — that is, the order of the character record must be the same order in which each unique character in the input string first appears.

For example, given the input string aabbbXccdd, the function should build a character record that looks like this:

Character	Count
a	2
b	3
X	1
c	2
d	2

Given the input string a🤣abbbXcc3dd, it should build a character record that looks like this:

Character	Count
a	2
🤣	1
b	3
X	1
c	2
3	1
d	2

Given the input string aabbccdd, it should build a character record that looks like this:

Character	Count
a	2
b	2
c	2
d	2

Once the function has built the character record, it’s time to move to the second stage, where it iterates through the character record in search of a character with a count of 1, and:

• If the function finds such a character, it exits the function at the first such occurrence, returning that character. For the input string aabbbXccdd, it returns X, and for the input string a🤣abbbXcc3dd, it returns 🤣.
• If the function doesn’t find any characters with a count of 1, it exits the function, having gone through every character in the character record, returning a null value (which in the case of Swift is nil).

Using a Swift OrderedDictionary

The character record is the key to making the algorithm work, and the key to the character record is that must be an ordered collection. If I add a, b, and c to the character record, it must maintain the order a, b, c.

This isn’t a problem in Python. While Python dictionaries have traditionally been unordered, as of Python 3.7, dictionaries maintain insertion order. In the previous articles covering this coding interview question, my Python solutions used a regular Python dictionary.

Because JavaScript runs in so many places in so many versions, I decided not to trust that everyone would be running a later version, which preserves insertion order. In the previous article, I wrote a JavaScript solution that implemented the character record using Map, a key-value data structure that keeps the items stored in the order in which they were inserted.

Swift’s built-in Dictionary does not keep the items in any defined order. Luckily, the Swift Collections package provides OrderedDictionary, which gives us both key-value storage and insertion order.

You’ll need to add Swift Collections to your project in order to use it. To do this, select File → Add Packages…

The dialog box for adding packages will appear:

Do the following:

• Enter swift-collections into the search field.
• Select swift-collections from the package list.
• Click Add Package.

You’ll be presented with a list of products within the Swift Collections package:

For this exercise, you’ll need only OrderedCollections, so check its box and click Add Package, which will add the package to your project.

Implementing the solution

Now we can implement the solution!

// We need this for `OrderedDictionary` 
import OrderedCollections

func firstNonRecurringCharacter(text: String) -> String? {
  var characterRecord = OrderedDictionary<Character, Int>()
   
  for character in text {
    if characterRecord.keys.contains(character) {
      characterRecord[character]! += 1
    } else {
      characterRecord[character] = 1
    }
  }
  
  for character in characterRecord.keys {
    if characterRecord[character] == 1 {
      return String(character)
    }
  }
 
  return nil
}

characterRecord, which keeps track of the characters encountered as we go character by character through the input string, is an OrderedDictionary. Note that with Swift, which is both statically and strongly typed, we need to specify that characterRecord’s keys are of type Character and its values are Ints.

After that, the implementation’s similar to my Python and JavaScript versions.

Previously in this series

• How to solve coding interview questions: Looking deeper into finding the first NON-recurring character in a string
• 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

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