First Non-Repeating Character is another interview question that has been asked by Amazon and several companies. Here you have to find first occurrence of aa non repeating character from a given string. You can solve in codesignal, leetcode and many other places. But if you are looking for a different solution than yours, here's how I solved it.

There are similar problems that can be solved with this same approach

  • Given a string, find the first non-repeating character and return the index
  • First Unique Character in a String and return the index

Problem

Given a string s consisting of small English letters, find and return the first instance of a non-repeating character in it. If there is no such character, return '_'.

Example

  • For s = "abacabad", the output should be
  • firstNotRepeatingCharacter(s) = 'c'.
  • There are 2 non-repeating characters in the string: 'c' and 'd'. Return c since it appears in the string first.
  • For s = "abacabaabacaba", the output should be
  • firstNotRepeatingCharacter(s) = '_'.
  • There are no characters in this string that do not repeat.

Solution

  • First create a map of the occurrence count for each item
  • In second loop we check which item was existed only once

Complexity: O(2N) = O(N)