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

//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;
}
2 Comments

Leave a Reply