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.
Table of Contents
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.
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.