Home » Technical Interview Questions » String Interview Questions » Find unique character in a string

Find unique character in a string



String

In Find unique character in a string problem, we have given a string containing only lower case alphabets(a-z). We need to find the first non-repeating character in it and print the index.

if no such character exists print -1.

Input Format

Only a single line containing string.

Output Format

Print the result in an integer format.

Constraints

  • 1<=|s|<=1000000
  • a<=s[i]<=z.
Example Input:
fwezfwjmevfukwejbfqegwkf
Example Output:
3

Explanation For Find unique character in a string

Store the count of the character in an array. Then run the loop from beginning till the end and check if a character whose count is 1 then print that index at we are and jump from the loop. Here is the count of each character which is listed below.

a- 0, b- 1, c- 0, d- 0, e- 4, f- 5, g- 1, h- 0, i- 0, j- 2, k- 2, l- 0, m- 1, n- 0, o- 0, p- 0, q- 1, r- 0, s- 0, t- 0, u- 1, v- 1, w- 4, x- 0, y- 0, z- 1.

Now, we traverse the string from the beginning and check if there is exist any character whose count is 1. Then we print the index of that character and terminate the loop and if we don’t find any character then print -1. Here we got z as count 1 so print the index of z which is 3.

Implementation For Find unique character in a string

/*C++ Implementation of First uique character in a string*/ 
#include<bits/stdc++.h>
using namespace std;
int main() 
{ 
    string s;
    /*take string as input*/
    cin>>s;
    int len=s.length();
    int freq[26];
    /*initalize all with 0*/
    memset(freq,0,sizeof(freq));
    for(int i=0;i<len;i++)
    {
        /*count the characters and store count of a at freq[0], count of b at freq[1], 
          count of c at freq[2],...,count of z at freq[25]*/
        freq[s[i]-'a']++;
    }
    int flag=0;
    for(int i=0;i<len;i++)
    {
        /*check the first character whose count is 1*/
        if(freq[s[i]-'a']==1)
        {
            cout<<i<<endl;
            flag=1;
            /*jump from the loop*/
            goto label;
        }
    }
    label:;
    /*if no character found as count 1 then print -1*/
    if(!flag)
    {
        cout<<-1<<endl;
    }
    return 0; 
}
Example Input 1:
dvcaewliabjvwdbgkinshckgfdbfcvd
Example Output 1:
4
Example Input 2:
aabbccdddeeefffrrrwwwqqqhhhfffihhi
Example Output 2: 
-1

Time complexity

O(L) where L is the length of the string.

READ  Convert String To Int

Space complexity

O(1) because we only create a constant array freq of size 26 which is less and we can say the space complexity is constant.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Abhishek

Abhishek was able to crack Microsoft after practicing questions from TutorialCup