# First non-repeating Character in a String

Return: L

• First non repeating character will have same first and lastindex in the string

``````public class Solution {
public int firstUniqChar(String g) {
for(int i=0;i<g.length();i++) {
char c =g.charAt(i);
if(g.indexOf(c)==g.lastIndexOf(c)) {
return g.indexOf(c);
}
}
return -1;
}
}
``````

• I feel like the solution by grvchik is less than optimal. The functions indexOf() and lastIndexOf() both do O(n) walks through the string. Which would lead to a time complexity of O(n^2). In ideal situations it would be faster, but we should account for the worst case.

My thought would be to use a hash map to store a vector of the indexes of the each letter.

Key: letter --> Value: Vector of ints

You could then go through the hash map entries, and only look at the ones with a vector of size 1. Then have a running minimum to find the lowest index.

This would have a time complexity of O(n). This would obviously be using more space because of the hash map.

• JS version using object (hashmap).

``````function solution (input) {
var obj = {};
for (let i = 0; i < input.length; i++) {
if (obj.hasOwnProperty(input[i])) {
obj[input[i]] += 1;
} else {
obj[input[i]] = 1;
}
}
for (let i = 0; i < input.length; i++) {
if (obj[input[i]] === 1) {
return input[i];
}
}
}
``````

• Since given input is all in caps.
I used char array of size 26 and tried solving in O(n)

LOGIC:
Counting the occurrence of each character. Whichever character has count=1 is the answer

Here is my Java Solution:
public static char firstNonRepaeating(String a)
{
char ans='0';
if(a.length()==0)
return ans;
int[] c=new int[26];
for(int i=0;i<26;i++)
c[i]=0;
for(int i=0;i<a.length();i++)
c[a.charAt(i)-'A']++;
for(int i=0;i<a.length();i++)
{
if(c[a.charAt(i)-'A']==1)
return a.charAt(i);
}
return ans;

``}``

• If the problem is expanded to included ascii characters or lowercase letters, the array solution won't work. The hash table solution works with any kind of character you throw at it.

• @reemak that's not actually correct, consider the test case googea, in you solution the array c will be populated in g, o, l, e,a positions as follows:
position 0 => a => 1
position 4 => e => 1
position 6 => g => 2
position 14 => o => 2

your code will return a as the first non repeating character, however the answer should be e cause it came in the input string before a

To correct your algorithm, you'll have to traverse the original string and for each char you check the count of it in the count array and return it if it's 1

• The approach described so far requires that we build another array or hashtable that hold the frequency of each character in the input string, then we would have to traverse the input string from the beginning again to get the first non repeating character.

There are three ways that we could implement this by traversing the input string only once.

Idea 1:
Use hashtable that preserve the order like LinkedHashMap in java to build your frequency map. After you're done building the map, you traverse it from the beginning looking for the first char with frequency 1, this will be your first non-repeating character.

Idea 2:
If you still want to use arrays, then instead of saving the frequency for each character, save along with it the first index where this character appeared, for example if we have google as input string we would have:

char: first index, frequency
e: 5, 1
g: 0, 2
l: 4, 1
o: 1, 2

What you have to do is to scan the frequency array and pick the one with the frequency = 1 and minimum index, in this case it will be l cause it has index 4 (came before e).

Idea 3:
Build 2 sets (use set that preserve order like LinkedHashSet in java) one that has the repeated characters and one that doesn't, then all you have to do after that is to pick the first character in the non-repeating hashset, pseudo code would be something like:

``````for each char c in input
if repeating set contains c
you could add c to repeating set if you want to maintain count, or just skip it
else if non-repeating set contains c
remove c from non-repeating set
else if non-repeating set doesnot contain c
``````

• ``````// using hashmap O(n)
public static Character getFirstNonRepChar(String args) {
Character ch = null;
Map<Character, Integer> map = new LinkedHashMap<Character, Integer>();
for(Character c : args.toCharArray()) {
if(map.containsKey(c)) {
map.put(c, map.get(c)+1);
} else {
map.put(c, 1);
}
}

for(Character c : map.keySet())
{
if(map.get(c) == 1) {
ch = c;
break;
}
}
return ch;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.