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++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
//Includes #include <iostream> //STD using namespace std; //Receives input string and its size char FirstNoneRepeated(char* str, int n) { //For each character in the string //compare it with all characters for (int i = 0; i < n; i++) { //This is to indicate that the //the current scanned character //has a repeated character in the //string int match = 0; //Search for a repeated character for (int j = 0; j < n; j++) { //Once a match is found no //need to continue searching //to the end of the string //also do not compare the character //with itself if (i != j && str[i] == str[j]) { match = 1; break; } } //If we finish searching for a match //for the currently scanned character //then we encountered the first none //repeated character if (match == 0) { return str[i]; } } //If we reach this point then all characters //are repeated in the string so return null //character return '\\0'; } //Main function void main() { //Should return (a) cout << FirstNoneRepeated("baby", 4) << endl; //Should return (b) cout << FirstNoneRepeated("bus", 3) << endl; //Should return null character cout << FirstNoneRepeated("ooo", 3) << endl; } |
Since there are no limitations in the question, I would like to try with:
1. sort the string first, then scan and find the one which is different from the characters next to it, O(nlogn)
2. use a table h[256] which is initialized to 0. Scan the string and increase the corresponding characters, such as h[‘b’]++. Scan the string again and look for h[ ] = 1. O(n).
What if you have the input string “bcba” then sorting that string gives you “abbc” then looping in this string will give you “a” as the first none repeating character however “c” in fact is the first none repeating character. My point the sort is a smart idea to do it but you loose track of the order. Sort is a good choice to remove duplicates regardless of their position.