Non repeating character string

Find non repeating character string

Develop an algorithm to print the first none repeating character in a string for example the first none repeating character in the string “baby” is “a”

Algorithm

A brute force method requires us to use two nested loops for character comparison. The moment we find a match we break the inner loop and continue with the next scanned character. If the inner loop finishes without finding a match then the index in the outer loop points to the first none repeated character. Sine we have two nested loops then the time complexity of this algorithm is O(n^2) where (n) is the string length. Pay attention to the fact that a character should not be compared to itself otherwise the algorithm will return wrong results in tricky cases such “aaa”. In the next article we will use a hash table to speed up this algorithm on the expense of extra space.

Code

Here is the code in C++

Tags:
2 Comments

Add a Comment

Your email address will not be published. Required fields are marked *