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.
O(n)
. \$\endgroup\$O(2n)
then... :-) \$\endgroup\$