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 last non repeating character in a given string.

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

Exam­ple:

String input = "algorithms tutorials"
Output: 'u'

String input = "aabbccdd"
Output: No repeating character found.

Approach:

Naive approach: This prob­lem can be eas­ily solved using two nested loops from right to left. Take each char­ac­ter from the outer loop and check the char­ac­ter in rest of the string using inner loop and return the first char­ac­ter which is non repeating(from right to left).  Time com­plex­ity is O(N^2).

Bet­ter approach: Using extra space

  • Iter­ate the string from right to left.
  • Count the occur­rence of each char­ac­ter and store it in a map.
  • Iter­ate the string again from right to left and check if the char­ac­ter has count = 1 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:

Out­put:

Last Non Repeating Character in 'algorithms tutorials' is: u

You may also like...