Community

Start a Thread
Filters
By Category
Notifications
Subscribe You’re not receiving notifications from this thread.

Find First Non-Repeating Character (Main Thread)

Here is the interview question prompt, presented for reference.

You're given a string of random alphanumerical characters with a length between 0 and 1000.

Write a method to return the first character in the string that does not repeat itself later on.

So if we had a string input of "asdfsdafdasfjdfsafnnunl'", we can see there are multiple letters that are repeated.

Executing firstNonRepeat('asdfsdafdasfjdfsafnnunl') should return 'j' since it's the first letter where there is no duplicate.

Constraints

  • The given string can be empty
  • The string will only contain lowercase/uppercase alphabets and numerals
  • Expected time complexity : O(n)
  • Expected space complexity : O(A) where A is the number of ASCII characters

You can see the full challenge with visuals at this link.

Challenges • Asked over 6 years ago by Jake from AlgoDaily

Jake from AlgoDaily Commented on Nov 30, 2017:

This is the main discussion thread generated for Find First Non-Repeating Character.

Jean Commented on Jan 16, 2021:

Hello! Why does the 2nd loop of the solution went through char in charCounter instead of char in str?
Afaik javascript object does not always guarantee insertion order. Which means by looping through charCounter there is a possibility you might not hit the actual first non-repeating character but one of the other non-repeating character, if any. But I might be wrong, so let me know. Thanks!

See this for object property order in js.

Jake from AlgoDaily Commented on Jan 22, 2021:

Hey Jean,

My bad and sorry for the late response! You're 100% correct, I've updated the solution code and added a node in the tutorial to reflect this.

ryanmvazquez@gmail.com Commented on Jan 20, 2022:

The answer to this question isn't really in the spirit of how this problem set is typically posed.

Unless prompted, interviewers typically do not want you to leverage the language-specific properties of data structures, only the properties of the data structures themselves. Hash maps etc. do not guarantee insertion order by their definition, only in their implementation.

Using these language-specific properties sidesteps the heart of this challenge and in most cases, interviewees would realize this is a non-trivial problem when forced to do without it!

Jake from AlgoDaily Commented on Jan 23, 2022:

The above comment is correct-- hash maps don't guarantee insertion order. I took a look at the solutions across all languages, and looks like in Python and PHP, we were traversing through the hash keys on the second loop. We should instead be traversing through the characters in the input string, since we want to find the first and order matters. This has been corrected!