Find first non-repetitive char in a string

I just had an interview for the C#.NET developer position and I was asked to find the first non repetitive char in a given string without using any library functions but just the basic constructs of the language such as fors and ifs.

I presented this solution considering the quick time constraint. I request evaluation of the solution of how truly it serves the question.

public static char findFirstNonRepetitiveChar(string input)
{
char c = '0';

for (int i = 0; i < input.Length; i++)
{
bool isdistinct = true;
for (int j = 0; j < input.Length; j++)
{
if (input[i] == input[j] && i!=j)
{
isdistinct = false;
break;
}
}
if (isdistinct)
{
c = input[i];
break;
}
}
return c;
}

• please give some examples of what is the input and what is the expected output. Oct 20 '16 at 2:43
• The question doesn't specify if the non-repetitive char must be non-consecutive or unique in the entire string. Oct 20 '16 at 6:33

first problem is, an empty string returns 0 as does :-

findFirstNonRepetitiveChar("000");


this is going to take a looooooong time :-

findFirstNonRepetitiveChar(new string('a', 500000) + new string('b', 500000));


Alternatives as suggested use hashtables which if you are going to use no library, are going to take a while to get going from scratch.

An alternative, but still pretty fast is to remove repeats from the string as you find them, this then becomes dependent on the number of different characters used...which for most normal text isn't too much, but for a devious unicode string, it could add up, I'm presuming using string.Replace and StringBuilder is a no no :-

        public static string Strip(string s, char c)
{
var r = new char[s.Length];
int i=0;
foreach (var b in s)
{
if (b != c) r[i++] = b;
}
return new string(r,0,i);
}
public static char? findFirstNonRepetitiveChar(string s)
{
int x = 1;
while (x < s.Length)
{
for (x = 1; x < s.Length; x++)
{
if (s[x] == s[0])
{
s = Strip(s, s[0]);
}
}
}
return (s.Length > 0)? (char?)s[0] : null;
}

• If you can't use string.Replace or StringBuilder you could just dump it into an array of char and operate on that. In fact, that's what I'd prefer. Oct 20 '16 at 14:22
• awesome answer @KeithNicholas. Oct 21 '16 at 22:37

Some of what constitutes a "good" solution here depends on how much value you place on (for example) CPU time vs. memory usage. Another point to take into account is what size of strings you expect to process, and whether you expect them to be mostly unique, mostly repeats, basically random, or exactly what.

As it stands, this uses almost no extra space, but uses $O(N^2)$ CPU time. If you expect the input strings to be long, this could be quite prohibitive.

If you didn't mind using extra space, you could (for example) walk through the string, and use a hash table to count the number of occurrences of each character. Then walk through the hash table, and find the characters in the string that only occur once. Mark those, then do a final walk through the string to find which occurred first. This requires two walks through the string, and one walk through a hash table the same size as the number of unique elements in the string, so it's basically 3N operations, or $O(N)$ (well, we expect linear complexity, anyway--in the true worst case, it's still $O(N^2)$). For a long string (say, a few million or even a few thousand characters) that could be a huge win (but at the expense of approximately doubling the memory usage. If you're concerned with worst case performance more than average, you might want to use a balanced tree instead of a hash table, so insertions are $O(N log N)$ (both expected, and worst case).

Which one is preferable will (mostly) come down to questions like those in the first paragraph. For typical short strings (less than 20 characters long is very common), either is likely to be fast enough that a more efficient algorithm won't make much real difference. On the other hand, if the input might be megabytes instead, the faster algorithm is likely to pay off--and even if it's several megabytes, allocating an extra several megabytes on a modern desktop (or server) machine rarely matters a whole lot.

• a hashtable is a library.....unless you intend for him to implement one? Oct 20 '16 at 5:10
• @KeithNicholas: Sure--why not. You can write one adequate for this job (no resizing, no removal) in probably 10 or 15 minutes. Then again, depending on the character set you need to support, you might be able to just use a simple array. Oct 20 '16 at 6:46

Questions

One of the most important things during an interview is the questions you ask. Not only it shows inquisitive thinking, but sometimes it can reduce the problem space. Questions to ask in this exercise:

• What to return if there is no distinct character?
• What is the size of the alphabet? Which is likely to be bigger: the size of the alphabet or the input?
• What is more important: time or space?

Even if you get answers like "doesn't matter", it's important to ask these questions, and to self-evaluate your solution in terms of these factors.

Algorithm

Your algorithm is fine if space is more important than time. For a faster solution, you can use extra storage to save time.

If the size of the alphabet is smaller than the input, you can use a simple array as a hash table to mark characters you've seen.

If the input is smaller than the alphabet, then you can make an array of characters from the input and mark all duplicates of each character in a single pass. (Similar to what @KeithNicholas suggested, but without the high memory churn of string concatenations.)

Implementation

Your implementation is quite fine, with a few minor issues:

• Why is '0' the return value if on distinct character is found?
• When you found a distinct character, instead of setting c and breaking out of the loop, it would be better to return input[i] directly
• Instead of isdistinct, simply distinct would be simple and natural
• i!=j is a bit too compact, i != j would be better
• Naming should be based on the .NET naming guidelines. So the methods name should be named using PascalCase casing. Compound words should be named using camelCase casing where each compound word would start with an upper letter. E.g isdistinct-> isDistinct.

• A public method should always validate its input parameters. Right now passing null to this method would blow with a NullReferenceException.

By slightly adjusting the nice algorithm from @KeithNicolas it can be a little faster. This adjustment involves

• change the for loop to a while loop
• initialize x with 1
• compare each character only to the first character
• setting x = 0 after the call to Strip()
• applying the mentioned points above

public static char? FindFirstNonRepetitiveChar(string input)
{
if (input == null)
{
throw new ArgumentNullException("input");
}

int x = 1;
while (x < input.Length)
{
if (input[x] == input[0])
{
input = Strip(input, input[0]);
x = 0;
}
x++;
}

return (input.Length > 0) ? (char?)input[0] : null;
}

• Passing "acacacacacacuacacacacauacacaBacacacauu" would result after the loop in "B"
• Passing "aaaaBcdcdcdcdcd" would result after the loop in "Bcdcdcdcdcd"

Another possible solution is to use an array as a lookup table for the characters, setting the position when we first find the character and setting it to an already found value if we find it again.

We need to offset the positions stored by 1 because position 0 is a valid position - we are making use of the fact that the int array is initialized to all 0 on creation and using 0 as Not yet found.

 public static class FirstNotRepeatingCharacterFinder
{
private const int LookupSize = (1 << 16)+1;
private static int[] Lookup;

private static void ResetLookup()
{
Lookup = new int[LookupSize];
}

public static int Find(string input)
{
if (string.IsNullOrEmpty(input))
return -1;

ResetLookup();
for (var index = 0; index < input.Length; index++)
{
if (Lookup[input[index]] == 0)
{
Lookup[input[index]] = index+1;
}
else
{
Lookup[input[index]] = -1;
}
}

for (var index = 0; index < Lookup.Length; index++)
{
if (Lookup[index] > 0)
{
return Lookup[index] - 1;
}
}
return -1;
}
}