What Is Non-Repeating Character In A String?

Introduction

The string is one of the most popular topics in programming job interviews. You will barely face a coding interview where the interviewer asks no string-based questions. 

A string is a sequence of characters in computer programming, either as a literal constant or variable.

Today, we’ll go over several approaches, ranging from brute force to optimal, for one of Amazon’s frequently asked questions.- “Find the first non-repeating character in a string.”

Problem Statement: Given a string or stream of characters, find the first non-repeating character, which implies getting the first character that is not occurring more than once in the string. 

The string will contain characters only from the English alphabet set, i.e., (‘A’ – ‘Z’) and (‘a’ – ‘z’). If there is no non-repeating character, print -1.  

Example: ‘cricketscenario’
Here the first non-repeating character is “k.”

Why is “k” the first non-repeating character?

• The character ‘c’ appears 3 times at the indices 0,3,8, and hence, “c” is repeating.
• The character ‘r’ is also appearing multiple times at indices 1,12 and, thus, repeating.
• The character ‘i’ is again appearing at the indices 2,13; thus, “i” is repeating.
• Now, the character ‘k’ appears once at index 4, and therefore, it is the first character of the string that is not repeating.
• So, we will simply print/return ‘k.’

Without further ado, let’s get started with the solution. Before that, we recommend you should try it on your own here, champ.

There are several methods to get the non-repeating character in a string, and we will see each one by one thoroughly.

Method 1: (Brute force approach)

Use two for loops for traversing and finding the first character that is not repeating.

Algorithm:

•      1. Take a for loop from zero to the last character of the string.
• Take another for loop inside this, and check if the current character occurs just once in the string.
• If the character you are checking occurs only once, return the character and break from the loops.
• If there is no such character, return -1.

Below, C++ code is given for your better understanding.

Code

#include <bits/stdc++.h>
using namespace std;
void firstnonRepeating(string str)
{
    int i,j,c=0;
    for(i=0;str[i]!='\0';i++)
    {
        //initialise count here so that complete string can be checked 
        //for each character
        int count=0;
        for(j=0;str[j]!='\0';j++)
        {
            if(str[i]==str[j])
            {
                count+=1;
            }
        }
        if(count==1)
        {
         cout<<"first non-repeating character in the string="<<str[i];
         c+=1;
         break;
        }
    }
    // If there is no repeating character return -1.
    if(c!=1)cout<<-1<<endl;
}
int main()
{
    string str="cricketscenario";
    firstnonRepeating(str);
    return 0;
}

• Time Complexity: O(n*n): This approach uses nested for loop. Therefore the complexity will be O(n*n).
• Space Complexity: O(1): No extra space is required. Therefore the space complexity will be constant.

If you’re having trouble calculating time and space complexity, check out this blog to learn everything you need to know about time and space complexity.

Method 2 (Optimised Approach using Array)

Create a Count array to store the frequency of characters, and wherever you find the value as ‘unity’ the first time, just return that character.

Algorithm:

• Create an array of size 256, the maximum type of characters possible, and initialize its values to 0.
• Take the character, move to its “ ASCII value” position in the array, and increase the frequency by 1.

Example:

a. Character is ‘k.’
b. Move to ‘107’ position in array as the ASCII of ‘k’=107
c. Increment the value by 1

Now traverse the created array, and once you get the frequency as unity, return the character associated to that position. Else, return -1.

Below, C++ code is given for your better understanding.

Code

#include <iostream>
using namespace std;
void nonRepeating(string str)
{
//create a count array to store the frequency of characters
     int arr[256];
     int c=0;
     for(int i=0;i<256;i++)
    {
        arr[i]=0;
    }
//take the character and move to the ascii value of that character and increment by 1
    for(int i=0;str[i]!='\0'; i++)
    {
        arr[int(str[i])]+=1;
    }
    
    for(int i=0;str[i]!='\0';i++)
    {
        if(arr[int(str[i])]==1)
        {
        cout<<"first non-repeating character in the string="<<str[i];
        //increment 'c' so that if it is 0 only, then print -1 
        c=+1;
        break;
        }
    }
    if(c!=1)cout<<-1<<endl;
}

int main()
{
    string str="cricketscenario";
    nonRepeating(str);
    return 0;
}

Time Complexity: O(n): The time complexity will be of order ‘n’ as we will be traversing the string twice, which is O(n+n)=O(2n).
As we know, constants are ignored asymptotically. So overall, the time complexity is O(n).
Space Complexity: O(n): We created an extra array as a count array to get the count of characters in the string, which will occupy order ‘n.’

Method 3 (Optimised Approach using Hashmap)

Use a hashmap to store the character and its frequency, and return the character whose frequency is found one.

Wondering what a hashmap is?

 Don’t worry. Learn Hashmap from Coding Ninjas for free here.

Algorithm

• Take an unordered_map which stores the character and its frequency
• Now, in the first part of the map is a character type that will store the characters, and the second part of the map is an integer type that will keep the frequency of characters.
• Now, simply traverse the created unordered_map and wherever you get the second part as unity, just print the character associated with it.
• If no character is non-repeating, then return -1.

Below, C++ code is given for your better understanding.

Code

void nonRepeating(char *str)
{
    //first part of map stores the character and
    //second part stores its frequency
    unordered_map<char,int>v;
    int c=0;
    for(int i=0;str[i]!='\0';i++)
    {
        //append the frequency of character
        v[str[i]]++;
    }
    for(int i=0;str[i]!='\0';i++)
    {
        //first time when frequency is 1 return the character 
        //associated to it
        if(v[str[i]]==1)
        {
        cout<<"first non-repeating character is="<<str[i];
        c+=1;
        break;
        }
    }
    //if c is still not 1 then no character was found 
    //non-repeating so print -1
    if(c!=1)cout<<-1<<endl;
}
int main()
{
    char s[] = "cricketscenario";
    nonRepeating(s);
    return 0;
}                         

Analysis of Time Complexity: O(n): The time complexity will be of order ‘n’ as we will be traversing the string twice, which is O(n+n)=O(2n).
As we know, constants are ignored asymptotically. So overall, the time complexity is O(n).
Analysis of Space Complexity: O(n) The created hashmap will occupy the space.

You are now aware of all possible approaches. Don’t forget to submit it to CodeStudio and have it accepted all at once.

Frequently Asked Questions

Key Takeaways

The main idea behind solving this problem to find the non-repeating character of the string is to use a count array or a hashmap to solve the problem efficiently. Preparing for the hiring process of big product-based companies from Google to Microsoft requires an endless amount of practising of problems. 

These interviews are deemed very hard to crack but hold the dreams of many budding software developers. So here is a compilation of all the must-do coding interview questions sorted topic-wise for your convenience in one place!

Remember to submit them to CodeStudio as well.

By Neerulata