Find first non repeating char in a string

Question

This is LeetCode question 387 if anyone is interested. The task is to accept a string and find the first char that appears only once, and return its index. If no char appears only once then return -1. Examples are:

input: "leetcode"
output: 0
input: "loveleetcode"
output: 2
input: "aabb"
output: -1

In the first example, 'l' is the first char that appears once, in the second example, 'v' is the first unique char. Here is the code I have:

public int FirstUniqChar(string s) 
{
 for (int i = 0; i < s.Length; i++)
 {
 bool success = Dup(s, s[i], i);
 if (success){
 return i;
 }
 continue;
 }
 
 return -1;
}
bool Dup(string s, char temp, int index)
{
 for (int i = 0; i < s.Length; i++){
 if (s[i] == temp && i != index)
 return false;
 }
 
 return true;
}

My biggest question about improving this code is, is there a way to enter the Dup function without iterating through the entire string again in Dup? Should I completely get rid of Dup? Inside of Dup I tried starting the loop at index and continuing but that would return a wrong response if the repeating chars happened to be back to back.

Let me know if this is better than using a double for loop. I believe this should be as a nested loop would make it 0(n^2) and I'm curious what this would be as it will return the correct value as soon as it is found rather than looping through every value and then determining.

Any suggestions are appreciated.

• stupidQuestions: I noticed there is another question asked on here today, I hope it is still appropriate to ask mine considering it is a different language and our logic is different. I am not using a Dictionary.
• Alexis Wilke: You can make it O(n).
• stupidQuestions: Making it 0(n), would that require a dictionary or hashmap and looping through adding each item to the dictionary and looping through again to find the value with the count of 1?
• Alexis Wilke: Yes, it would require a dictionary. I guess that means O(2n) then... :-)
• stupidQuestions: Well I guess that technically 0(2n) would be an improvement.

Answer 1

Other than applying the suggested variable and method naming changes for code clarity, you could store the duplicated characters in a hashset so that you can avoid evaluating those.

In addition, this also enables evaluating only the remaining part of the string from the index you are currently on, instead of going through the whole thing every time.

int GetTheIndexOfTheFirstUniqueCharacter(string s)
{
 var repeatedCharacters = new HashSet<char>();
 for (int i = 0; i < s.Length; i++)
 {
 if (!repeatedCharacters.Contains(s[i]))
 {
 if (IsUnique(s, s[i], i))
 {
 return i;
 }
 else
 {
 repeatedCharacters.Add(s[i]);
 }
 }
 }
 return -1;
}
bool IsUnique(string s, char temp, int index)
{
 for (int i = (index + 1); i < s.Length; i++)
 {
 if (s[i] == temp)
 {
 return false;
 }
 }
 return true;
}

Answer 2

With LINQ you can achieve the same with the following fairly concise query:

int GetTheIndexOfTheFirstUniqueCharacter(string input)
{
 char? firstUnique = input
 .ToCharArray()
 .GroupBy(character => character)
 .FirstOrDefault(charGroup => charGroup.Count() == 1)
 ?.Key;
 return firstUnique.HasValue ? input.IndexOf(firstUnique.Value) : -1;
}

• We are converting the string to a character array to able to use LINQ
• Then we group the characters in the same order as they appear in the input

The IGrouping<TKey,TElement> objects are yielded in an order based on the order of the elements in source that produced the first key of each IGrouping<TKey,TElement>. Elements in a grouping are yielded in the order they appear in source.

• We retrieve the first group where the group contains only a single element
• If there is such then firstUnique will have a value otherwise it will be null
  • If firstUnique has value then we can find the related index with the IndexOf
  • Otherwise we return with -1

---

Obviously, this is not the most performant solution, but it's simple and easy to understand.