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

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

Exam­ple:

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

String input = "algorithms"
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 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 left to right 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.
  • Time com­plex­ity is O(N) and Space Com­plex­ity is O(N).

Com­plete Code:

Out­put:

First Repeating Character in 'horizon' is: o

You may also like...