Given a string find its first non-repeating character


StringViews 3922

Given a string, write a function to find the first non repeating character

Example

INPUT
s = “tutorial cup”

OUTPUT
‘o’ is the first non-repeating character

Method 1

Time Complexity : O(n)

Algorithm

1. Scan the input string and construct a character count array from input string
ie, In the above example,
count of t is 2, so count[‘t’] = 2
count of u is 2, so count[‘u’] = 2
count of o is 1, so count[‘o’] = 1

2. Again, scan the input string and print the first index from the count array which have value equal to 1.
ie, In above example,
indexe ‘o’ is having value equal to 1

Method 2

This method is an improvisation to the above method.

In the above method, the string is scanned twice. What if the string length is very big (for example, string length is 1 million) and the non-repeating character is at the end. It will take so much time, so  step1 in above method will be same but in step2, instead of scanning string we will scan count array (which is of length 256)

In count array instead of just storing counts we will also store the index of the first time you encounterd the character

Ex: (4,78) for ‘z’, that is z has counted 4 times and the first time it was seen is at position 78 in the string.

C++ Program

#include <bits/stdc++.h>
#include <limits.h>
#define NO_OF_CHARS 256
using namespace std;
//Here position is the first occurence of that character
struct countposition
{
	int count;
	int position;
};
void firstNonRepeatingChar(char *s)
{
	int res = INT_MAX;
	countposition* count = new countposition[NO_OF_CHARS];
	for(int i=0; i<strlen(s); i++)
	{
		(count[s[i]].count)++; //increment the count of each character by using ASCII of character as key	
		//storing the position of the first occurencce
		if (count[s[i]].count == 1)
		{
			count[s[i]].position = i;
		}
	}
	//In count array, if count is 1 and position is least then update	
	for(int i=0; i<NO_OF_CHARS; i++)
	{
		if(count[i].count == 1 && res > count[i].position) //if count is 1, then print and break
		{
			res = count[i].position;
		}
	}
	cout<<s[res]<<" is the first non-repeating character "<<endl;
}

int main()
{
	char s[]  = "tutorial cup";
	cout<<"Input string is "<<s<<endl;
	firstNonRepeatingChar(s);
}

Try It

 

Algorithm

1. Scan the input string and construct a character count array from input string
ie, In the above example,
count of t is 2, so count[‘t’] = 2
count of u is 2, so count[‘u’] = 2
count of o is 1, so count[‘o’] = 1

2. Traverse through the count array

a. If the count is equal to 1 and the first occurrence is least, then print that character

C++ Program

#include <bits/stdc++.h>
#define NO_OF_CHARS 256
using namespace std;

void firstNonRepeatingChar(char *s)
{
	int* count = new int[NO_OF_CHARS];
	for(int i=0; i<strlen(s); i++)
		count[s[i]]++; //increment the count of each character by using ASCII of character as key	
	for(int i=0; i<strlen(s); i++)
		if(count[s[i]] == 1) //if count is 1, then print and break
			{
			cout<<s[i]<<" is the first non-repeating character "<<endl;
			break;
			}
}
int main()
{
	char s[]  = "tutorial cup";
	cout<<"Input string is "<<s<<endl;
	firstNonRepeatingChar(s);
}

Try It

 

Translate »