What Is Non-Repeating Character In A String?

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 Coding Ninjas Studio and have it accepted all at once.

Also read,  Tribonacci Series and Short int in C Programming

Frequently Asked Questions

How do you find non-repeating characters in a string?

The idea is to create an extra array using a hashmap or creating a count array and simply counting the frequency and returning the first character with frequency as unity.

What is a non-repeating character?

A character that appears a single time in the string is said to be a non-repeating character.

Is string a data structure?

A string is a data type implemented as an array of different characters.

How do you find non-repeating characters in an array?

The idea is you can either use any of the two methods discussed above or even use two loops as- one for the current character and another loop to check whether the character appears again in the array or not.

Why is a string called immutable?

A string is called immutable because if created once, it cannot be changed. In simple words, once a string is created later, you can not change the string object.

Conclusion

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. 

Recommended Problem - K Closest Points To Origin

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 Coding Ninjas Studio as well.