Algorithms: Find the First Non-Repeating Character

Algorithms: Find the First Not-Repeating Character

In this article, we’ll present an algorithm challenge and then provide two solutions: a runner-up and the optimal algorithm. The algorithms are written in Python.

The Challenge

Find the first non-repeating character in a string of lowercase letters. Non-repeating is defined as a character that only appears once in the string. If all characters repeat, return an underscore.

Here are some sample strings and the answer for each:"aabcdb" # c
"abcddc" # a
"aabbcc" # _
"abbcda" # c

Now that we understand the challenge, I’d encourage you to try on your own.

If you’ve already tried or you want to skip ahead, then let’s get to the solution!

Runner-Up

Using a pair of for loops, we can iterate over the string in a nested fashion to determine if a character has been repeated:

A few notes on this solution:

• The nested for loop algorithm has a polynomial time complexity of O(n^2).
• Optimize nested loop solutions by reducing the algorithm to a single loop.

Optimal Solution

To avoid having a nested loop, we can keep track of how many times each value exists in the string using a dictionary — where the character is the term and the count is the definition.

Once we have our counts, the dictionary becomes a reference as we check for the first character with only one occurrence:

Some notes about this solution:

• Since a dictionary is by definition unordered, we should loop through a second time to ensure we maintain the sequence of the string.
• Starting in version 3.7, Python dictionaries will preserve the entry order. This would eliminate the need to loop through the string and allow us to directly iterate over the dictionary instead.

Bonus Solution

Fortunately for us Pythonistas, there are native string functions that make this algorithm a breeze.

Using .find() and .rfind(), we can determine the index from the left and right of a character. If the left and right searches return the same index, then we can conclude there is only one occurrence of the character.def firstNotRepeatingCharacter(my_string):
 for c in my_string:
   if my_string.index(c) == my_string.rindex(c):
     return c
 return "_"

Some notes about this solution:

• Since the algorithm relies on language-specific methods, it is not language-agnostic.
• While this algorithm syntactically has less iteration than our optimal solution, the two share the same time complexity.

Conclusion

How did it go for you? What was your initial solution? Share your experiences below!

A special thanks to Nick White for his explanation of this algorithm!