Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Find the first non repeating character in a given string

Objec­tive: Given a string, write an algo­rithm to find the first non repeat­ing char­ac­ter in it.

Exam­ple:

String input = " tutorial horizon"

Output: 'u'

String input = "aabbccadd"

Output: No repeating character found.

Approach:

Naive approach: This prob­lem can be eas­ily solved using two nested loops. Take each char­ac­ter from the outer loop and check the char­ac­ter in rest of the string using inner loop and check if that char­ac­ter appears again, if yes then con­tinue else return that char­ac­ter.  Time com­plex­ity is O(N^2).

Bet­ter approach: Using extra space

  • Iter­ate the string from left to right.
  • Count the occur­rence of each char­ac­ter and store it in a map.
  • Iter­ate the string again from left to right and check if the char­ac­ter has count = 1 one in the map cre­ated in the pre­vi­ous step, if yes then return that character.
  • If none of the char­ac­ter has count = 1 in map, return null.

Com­plete Code:

Output:

First Non Repeating Character in 'tutorial horizon' is: u

You may also like...