Categories
Career Programming

How to solve coding interview questions: The first NON-recurring character in a string

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:

CharacterNumber of times it appeared in the string
a2
🤣1
b3
X1
c2
31
d2

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

11 replies on “How to solve coding interview questions: The first NON-recurring character in a string”

I am not sure your second approach works. 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.

Hi Joey, thanks for these thought exercises. Here’s an alternate solution in JS, using Sets (of which I learned about in your previous post, I didn’t know JS already had them):

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;
}

BTW in looking up the docs of set I learned of the “of” operator for iteration, I found it very useful.

Both your solution and mine depend on the fact that JS’ Set and Python’s dict.keys() both iterate in insertion order; otherwise another kind of structure would be needed for us to be able to fetch the first-recorded unique character.

My TypeScript solution:

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;

}

Worry not, Dan! The comments engine doesn’t understand Markdown, but it does understand HTML. I edited your comment by putting your code in a <pre> tag, which fixed it.

By Post Author

Comments are closed.