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

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

Exam­ple:

String input = "horizon tutorials"
Output: 'i'

String input = "algorithms"
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 repeat­ing.  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 right to left and check if the char­ac­ter has count more than 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:
Last Repeating Character in 'tutorial horizon' is: o

You may also like...