Given a string, find first non-repeating character

Some examples

Before we write the code lets, look into some examples of this program.

Input

A=’bookbook’

Output

All the characters are repeating

Input

A=’Coding Ninjas Studio’

Output

‘c’

Code in c++

# include<iostream>
# include<climits>
 
using namespace std;


int first_non_rep(string s) {
    int fi[256]; 


    for(int i = 0; i<256; i++)
        fi[i] = -1;


    for(int i = 0; i<s.length(); i++) {
        if(fi[s[i]] == -1) {
            fi[s[i]] = i;
        }else {
            fi[s[i]] = -2;
        }
    }
 
    int res = INT_MAX;
 
    for(int i = 0; i<256; i++) {


        if(fi[i] >= 0)
            res = min(res, fi[i]);
    }


    if(res == INT_MAX) return -1;
    else return res;
}
 
int main(){
    string s;
      s= "goodmorning";
      cout<<s<<endl;
    int firstIndex = first_non_rep(s);
    if (firstIndex == -1)
        cout<<"Either all characters are repeating or string is empty";
    else
        cout<<"First non-repeating character is "<< s[firstIndex];
     
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

goodmorning
First non-repeating character is d

Algorithm complexity

Time complexity: O(n)

Space complexity: O(n)

Also read, Application of Oops

Approach(Optimised solution)

The approach to this program is simple.

• First, the user will enter the string.
• We will traverse the string using two loops.
• The first loop will scan each character of the string, and the second loop will find the occurrence of that character in the rest of the string.
• If the string is not occurring, it is the first non-repeating character, and we will print it.
• If the string occurs, we will keep traversing the string until the last character is traversed.

Some examples

Before we write the code lets, look into some examples of this program.

Input

A=’codecode’

Output

All the characters are repeating

Input

A=’Coding Ninjas Studio’

Output

‘c’

Code in c++

#include<iostream>
using namespace std;
#define NO_CHAR 256

int *get_char(char *s)
{
	int *count = (int *)calloc(sizeof(int), NO_CHAR);
	int i;
	for (i = 0; *(s+i); i++)
		count[*(s+i)]++;
	return count;
}

int non_rep(char *s)
{
	int *count = get_char(s);
	int index = -1, i;
	for (i = 0; *(s+i); i++)
	{
		if (count[*(s+i)] == 1)
		{
		index = i;
		break;
		}
	}
	free(count);
	return index;
}


int main()
{
	char s[NO_CHAR];
	cout << " \nEnter the string : ";
	cin >> s;
	int index = non_rep(s);
	if (index == -1)
		cout << "All the characters are repetitive";
	else
		cout << "First non-repeating character is " << s[index];
	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Enter the string: helloworld
First non-repeating character is h

You can try by yourself with the help of online C++ Compiler.

Algorithm complexity

Time complexity: O(n)

Space complexity: O(n)

Note: Both the approaches have the same space and time complexity. In an optimized solution, the time complexity can be improved in practice. The first part of the algorithm constructs the count array by traversing through the string.

Also check out - Substr C++

Frequently asked questions

1. What do you mean by an array?
   An array is nothing but a collection of items stored at contiguous memory locations.
2. What is calloc() function?
   Calloc() function is a function in c++ used to allocate a block of memory to an array and initialize all its bits to zero.
3. What is a sting in an array?
   A string is silimar to an array, but an array has a fixed size while a string has a variable size. String usually contains ASCII characters.

Conclusion

In this article, we have discussed the problem of finding the first non-repeating character in a string. We have used the c++ language to solve this problem. We have also discussed the time complexity and space complexity of the approach. 

Check out this article - C++ String Concatenation

Recommended problems -

• Find the Shortest Substring in a String
• Subsequence of a String
• Beautiful String

Also read -  Decimal to Binary c++

We hope that this blog has helped you enhance your knowledge regarding program to find first non-repeating character in a given string and if you would like to learn more, check out our articles on c++. Do upvote our blog to help other ninjas grow. Happy Coding!”