First unique character in a string | Leetcode #387

This video explains a very interesting programming interview question which is to find the first non-repeating character in a string. The problem is simple but has repeated in numerous interviews. I have shown the intuition for solving this problem with proper examples and algorithm. We can solve this problem using an array or hash or map etc. data structures. I have shown the solution using simple array in just O(N) time and O(1) extra space. CODE LINK for this is given in the description below. I have also given link for similar problem variants ransom note and first non repeating character in a stream of characters. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

SIMILAR PROBLEMS:-

[indraalapati]

We can also do something like this in java ->
for (int i = 0; i < s.length(); i++) {
Character ch = s.charAt(i);
if (s.indexOf(ch) == s.lastIndexOf(ch)) {
return i;
}
}
return -1;

[nagajaswanth]

did it in python by using sets:
class Solution(object):
def firstUniqChar(self, s):
s=list(s)
c=0
j=set([])
while len(s):
i=s[0]
if i in j:
c+=1
s.remove(i)
continue
p=set(s)
s.remove(i)
k=set(s)
if len(p)==len(k):
c+=1
j.add(i)
continue
else:
return c
return -1

[PersistentProgrammer]

I solved this question using dictionary, below is my Python Code -


class Solution:
def firstUniqChar(self, s: str) -> int:
str_dict = {}
for ch in s:
if ch not in str_dict:
str_dict[ch] = True
else:
str_dict[ch] = False

for i, c in enumerate(s):
if str_dict[c]:
return i
return -1

[sangdilbiswal]

int firstUniqChar(string s) {
vector<int> f(26);
for(auto x: s) f[x-'a']++;
for(int i = 0 ; i<s.size(); i++) if(f[s[i]-'a'] ==1) return i;
return -1;
}

[ShreyaSingh-vrqi]

Can we do it in only 1 traversal, we start traversal from: s.length()-1 to 0 and whenever we find a character occuring first time we can update the our answer. At last we will have the first unique character from left side?

[borat_trades]

i use Counter from collections. much simpler. but your approach is also good - alternative vision.. using alphabet 0 26.
my code:
from collections import Counter
class Solution:
def firstUniqChar(self, s: str) -> int:
t = Counter(s)
t = dict(t)
index = -1
for i in range(len(s)):
if t[s[i]] == 1:
index = i
break
return index

[muditkhanna]

you should used the break statement in this code because that would stop it to time complexity to go to 0(n^2)

[fatimajaffal]

a first time, we have same solution :D

[vnm_]

function {
let map = {};
for (let i = 0; i < input.length; i++) {
if (map[input[i]] !== undefined) {
return input[i]
} else {
map[input[i]] = i;
}
}
return undefined
}

[switoocool]

I think your solution will not give first unique character in case if string is "abzbac". Your code will return 'c' although first non unique character is 'z'.

[alphabeta]

I think hashtable can come handy for this problem

[aniruddhabhattacharya]

Another approach is to use the pairs but the logic is similar:-
class Solution {
public:
int firstUniqChar(string str) {
pair<int, int> arr[26];
for (int i = 0; i<str.length(); i++)
{

arr[str[i]-(int)'a'].second = i;
}
for (int i = 0; i < str.length(); i++)
{
if (arr[(int)str[i] - (int)'a'].first == 1)
return i;
}
return -1;
}
};

[aviligondagowtham]

When we got job in company these problems are useful in company or not

[sanjay]

Nice. How to use a map in C++ instead of an array?

[sakthim]

Why don't you use the same approach for first non repeating character in a stream of character?
I think we can solve that problem also in the same manner.

[PriyaKumari-yzwv]

It will not always return the first character. if the string is "cabs" then this approach will return an instead of c since in array we are storing always in fashion

[slowedReverbJunction]

Ye aapne freq[ s[i] - 'a' ] +=1 kyun kia hai
Smjh ni aara

[kushagrajain]

My Python Solution
class Solution:
def firstUniqChar(self, s: str) -> int:
dict = {}

for ch in s:
if(ch in dict.keys()):
dict[ch] = -1
else:
dict[ch] = s.find(ch)

minimum = -1
for val in dict.values():
if( (minimum == -1 or minimum > val) and val != -1 ):
minimum = val

return(minimum)

[balajivenky]

def firstUniqChar(s: str) -> int:
mydict = {}
for i in s:
if i in mydict:
mydict[i] += 1
else:
mydict[i] = 1
cnt = 0
for i in s:
if mydict[i] <= 1:
return cnt
cnt +=1
return -1

[ramnathan]

similar approach could be done using dictionary as of in python