How to solve coding interview questions: Finding the first NON-recurring character in a string in Swift : Global Nerdy

This reminds me of what happened in my worst interview.

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`	`🤣`
aab`bccdd`	`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.

The algorithm

Using a Swift OrderedDictionary

Implementing the solution

Previously in this series

4 replies on “How to solve coding interview questions: Finding the first NON-recurring character in a string in Swift”

Using a Swift `OrderedDictionary`