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...