First Unique Character in a String


This problem is one of the competitive questions dealing with strings, so as indicated by the title we need to find first unique i.e non-repeating character in a given string and return the index or else if no such character exists we return -1.
Note: We are considering only lowercase, if asked with uppercase or camelcase full string can be converted to lowercase.

Example :

Input : opengenus
Output : 0
# unique character ' O ' at position zero

Input : hellhell
Output : -1
# no unique character all are repeated 

Solution Approach

So the solution for this problem can be obtained by counting the occurrence of each character in a string and we are looking for unique characters so it must occur only once in the whole string and even if there is more than one of such characters we need the first one.

Steps

  1. Iterate through each character in the string
  2. Flag/note each occurance of the characters
  3. Next, we find out which character occurs only once and then return it's position
  4. Else, if there are no unique characters we return -1

Explanation

  • Iteration through the whole string can be done with the help of a simple for loop till the end i.e size/length of the string.

  • There are 26 alphabets and each needs to be flagged or counted the no.of time they occur, this can be done with an array. ASCII values of a - z lie between 97 - 122 so if we subtract 97 from it we get the index value of the letter like 0 for a and 1 for b and so on. Now we will flag them by incrementing the array at each poition of occurance like if the string isaa then consider an array arr[] to flag them and s is the string and i is iteratorin loop then, arr[s[i]-97] gives first s[i] is a, then a-97 results in zero then arr[0]++; is flagged thus more the occurances more the value.

  • Now, we can iterate through the array arr and find which occurs only once else we return -1.

Pseudocode

  1. Start
  2. Read the input string of letters from the user
  3. Create an [flag array]array of size 26 for each alphabet
  4. Initialize all the values of flag array to zero
  5. Iterate through each letter in the string
  6. At each iteration for every occurance of an alphabet increase the flag value
  7. The postion of flag is based on the alpahbet (a=1, b=2...z=26)
  8. After complete iteration find the first flag value = 1 i.e the alphabet appers only and print it
  9. If there is no such value return -1
  10. Exit

Program in C++

Following is the C++ implementation:

#include <iostream>

using namespace std;

int firstUniqueChar(string s) {
        int j;
        int a[26]={0};
        for(j=0;j<s.size();j++)
 	        a[s[j]-97]+=1;    
        for(j=0;j<s.size();j++)
        {
            if(a[s[j]-97]==1)
                return j;
        }
        return -1;
    }

int main()
{
    string s;
    cin>>s;
    int ans;
    ans=firstUniqueChar(s);
    cout<<ans;
    return 0;
}

Example Step by Step Explaination

Input : opengenus

string=opengenus

  • First we create an array flag with 26 values initialized to zero
  • Each postion represent an alphabet so the array represents
a b c d ..  z
0 0 0 0 ..  0
  • Now we iterate through each letter of the word and increase the flag values
o p e n g e n u s
flag[string[position]-97] => flag[(ascii value)-97] => flag[pos]++
  1. ' o ' flag[string[0]-97] => flag[111-97] => flag[14]++ (incremented) flag[14]=1;
  2. ' p ' flag[string[1]-97] => flag[112-97] => flag[15]++ (incremented) flag[15]=1;
  3. ' e ' flag[string[2]-97] => flag[101-97] => flag[04]++ (incremented) flag[04]=1;
  4. ' n ' flag[string[3]-97] => flag[110-97] => flag[13]++ (incremented) flag[13]=1;
  5. ' g ' flag[string[4]-97] => flag[103-97] => flag[06]++ (incremented) flag[06]=1;
  6. ' e ' flag[string[5]-97] => flag[101-97] => flag[04]++ (incremented) flag[04]=2;
  7. ' n ' flag[string[6]-97] => flag[110-97] => flag[13]++ (incremented) flag[13]=2;
  8. ' u ' flag[string[7]-97] => flag[117-97] => flag[20]++ (incremented) flag[20]=1;
  9. ' s ' flag[string[8]-97] => flag[115-97] => flag[18]++ (incremented) flag[18]=1;
  • Now from the beginning we look for values in flag = 1
    This means that the alphabet has occured only once.

  • So we get flag[14]=1 so the 14th letter ' o ' is our answer

  • OUTPUT : o [First Unique Character in the given String]

Thoughts and different approaches

There might be many other ways to solve this problem but in this approach I tried to explain the logic as simple as possible, we can use this logic in similar scenarios and keep exploring and learn new methods. The above method is called as hashmap method for this types of problem we can also try other ways like using dictionaries in Python or using minimum index value with Java and any other languages.

With this article at OpenGenus, you must have the complete idea of the algorithm to find the First Unique Character in a String. Enjoy.