Find the first non-repeating character in a string: ("DEFD" → E)

Testing more than one thing

Looking at some of your tests, you you are testing more than one thing. You are also testing contradictory things. This makes the purpose of your tests less obvious. Consider:

[TestMethod()] public void FindFirstNonRepeatingCharacterTestMixedCasing() { string testString = "EeFd"; char testChar = BlueWolfSolutions.FindFirstNonRepeatingCharacter(testString); Assert.IsFalse(testChar == 'E' && testChar == 'D'); Assert.AreEqual('F', testChar); } 

The important test is:

Assert.AreEqual('F', testChar); 

By definition, if testChar is 'F', it can't be 'E' or 'D', let alone both 'E' and 'D'... why bother testing the IsFalse condition, it just muddies the water?

The FindFirstNonRepeatingTestWhiteSpace is particularly confusing as to what the intention of the test is, because you're not only testing true and false conditions on one of the variables, you're also calling the function under test with multiple strings. Keep your tests simple and try to focus on just testing one intention per test.

Naming

Naming is also quite important in tests to help get the purpose of the test across. Rather than testChar, perhaps firstRepeatedCharacter would have been a more expressive variable name.

Code

Was that case-insensitive aspect an assumption from your side, or was this part of the requirements? If not, did you ask? What were the exact requirements anyway?

The code is fairly verbose. The method and variable names are descriptive, which is good, but some of the names are a bit too long for my taste.

You can iterate a string directly, you don't need to create a character array:

for (int i = 0; i < str.Length; i++) char c = str[i]; ... 

You can also use a foreach loop:

foreach (char c in str) ... 

Returning a space if there's no non-repeating character means that you can't distinguish between such input and input where a space is the first non-repeating character. I'd change the return type to char? and return null if there's no match.

There's no need to declare nonRepeatingCharacter up-front. Declare it where you actually need it. In fact, you don't need it at all: instead of breaking out of the second loop you can simply return that character directly.

The algorithm itself is fairly straightforward. You could improve performance for large inputs where non-repeating characters occur relatively late by keeping a list of characters in order of their first occurrence. You then only need to iterate that list after building the character-counts dictionary, instead of iterating the full input again. I wouldn't do that without first making sure that performance is a concern though.

Tests

You're mostly testing casing and spacing, both of which depend a lot on the requirements you were given, so without knowing the requirements I'm not sure about their value.

I'd give the empty string a test of its own, because it's a typical edge-case. The same goes for other inputs that do not contain non-repeating characters.

As forsvarir already mentioned, your AreEqual and IsTrue assertions are sufficient. The IsFalse assertions only add clutter.

In coding assignments, it's not always about if you can devise and implement an algorithm, but also about if you know how to avoid inventing a wheel. Leveraging the standard API as much as you can will show you know your language.

How about something like

foreach (char c in str) { if ( str.IndexOf(c) == str.LastIndexOf(c) ) { return c; } } 

To show extensive understanding, you'd say/document that this solution has complexity of O(n²) and may have to be revisited if/when performance requirements are added.

They provided no constraints in the task as to performance or resource usage, and none about the input to be processed.

That's not saying that "performance" is not an indicator at all. But it has to be judged reasonably. If an algorithm exists with O(n*log(n)) no one will blame you for your implementation with O(n²). O(n³) might even be accepted, O(n^4) probably not.

An important skill in software development is to be able to find the right compromise between different aspects. Much of this comes only through experience. In your example, it's simply not required to produce an optimum performance solution. In a case like that, you go for the one with acceptable performance and best clarity, maintainability &c.

You don't need to count the number of occurrences of each character, you just need to know if a character is repeating or not, so you can use Dictionary<char, bool> instead of Dictionary<char, int>, but IMO using two List<char> gives more readable and clean code.

public static char FindFirstNonRepeatingCharacter(string input) { if (input == null) throw new ArgumentNullException(); var repeatingChars = new List<char>(); var candidates = new List<char>(); foreach (var i in input) { var c = char.ToUpperInvariant(i); if (repeatingChars.Contains(c)) continue; if (candidates.Contains(c)) { candidates.Remove(c); repeatingChars.Add(c); } else { candidates.Add(c); } } if (candidates.Count == 0) throw new Exception("No non-repeating characters"); return candidates[0]; } 

Algorithm Complexity

Ignoring the Assumptions made (Case doesn't matter), the tests and other triviality mentioned in other answers... Something no one else has mentioned: Your algorithms actual complexity.

Your algorithm is 2N - which means that you run through the entire "givenString" twice. In a string of 1 million characters, you could go through 2 million iterations: assuming the non-repeater is at/near the end of list. You go through the string twice.

You can adjust your algorithm to go through the list 1N + M (M being distinct number of characters... 26 for letters only, no case... 52 for upper lower.)

My Version

In my version, I remove all extraneous temp variable - no need for anything except input string and tracking dictionary. I'm following your "assumption" that case doesn't matter, although adjusting that (removing the ToUpper) is simple enough.

In my version, I'm not "counting" characters. The dictionary has a "Key" character and "Value" of the "Index" of a value seen for the first time... or -1 meaning it's been seen twice.

At the end, remove/ignore all the -1s... and get the min value - and corresponding Key/Character. (I'm sure this could be made more efficient, but I'm more just spit-balling here. I could make the "-1" into "Length" and just get "Min value > length" for example)

 static void Main(string[] args) { Console.WriteLine($"Input: EeFd"); Console.WriteLine($"Desired Result: F"); Console.Write($"Actual Result: "); Console.WriteLine(FindFirstNonRepeatingCharacter("EeFd")); Console.ReadLine(); } public static char FindFirstNonRepeatingCharacter(string givenString) { givenString = givenString.ToUpper(); Dictionary<char, int> charCounter = new Dictionary<char, int>(); for (int index = 0; index < givenString.Length; index++) { var c = givenString[index].ToUpper(); if (!charCounter.ContainsKey(c)) { charCounter.Add(c, index); } else { charCounter[c] = -1; } } return charCounter.Where(kvp => kvp.Value != -1).OrderBy(kvp => kvp.Value).First().Key; } 

Final Thoughts

For big strings, the difference between 2N and 1N+M would be non-trivial.

2(1million) = 2million. 1million + 26 = 1million and 26. 

Add other tidbits from the other answers, but I'm willing to bet money this (and possible a bad assumption) are the "killers" for your answer.

Further Thoughts

I'd also try to add some short circuits for "easy" answers (0/1/2 length strings) and verification that the string isn't ALL duplicates.

 static void Main(string[] args) { Console.WriteLine($"Input: EeFd"); Console.WriteLine($"Desired Result: F"); Console.Write($"Actual Result: "); Console.WriteLine(FindFirstNonRepeatingCharacter("EeFd")); Console.WriteLine($"Input: EEEE"); Console.WriteLine($"Desired Result: "); Console.Write($"Actual Result: "); Console.WriteLine(FindFirstNonRepeatingCharacter("EEEE")); Console.ReadLine(); } public static char FindFirstNonRepeatingCharacter(string givenString) { /* Short circut some small cases */ if (givenString == null) return ' '; if (givenString.Length == 0) return ' '; if (givenString.Length == 1) return givenString[0]; var charCounter = new Dictionary<char, int>(); for (int index = 0; index < givenString.Length; index++) { var c = givenString[index].ToUpper(); if (!charCounter.ContainsKey(c)) { charCounter.Add(c, index); } else { charCounter[c] = givenString.Length; } } var removeDuplicates = charCounter.Where(kvp => kvp.Value != givenString.Length); if (removeDuplicates.Any() != 0) return removeDuplicates.OrderBy(kvp => kvp.Value).First().Key; else return ' '; } 

I would recommend using a Dictionary in this type of scenario as a key lookup is faster and more efficient than multiple loops through the string chars in both directions. I tested the code below using a 100 character string and it completed in 0.0006876 seconds.

private char FindFirstNonRepeatChar(string testString) { Dictionary<char, char> characters = new Dictionary<char, char>(); Dictionary<char, char> repeatedCharacters = new Dictionary<char, char>(); foreach (char ch in testString) { char value; if(!characters.TryGetValue(ch, out value)) { characters.Add(ch, ch); } else if(!repeatedCharacters.ContainsKey(ch)) { repeatedCharacters.Add(ch, value); } } foreach (char ch in testString) { char value; if (!repeatedCharacters.TryGetValue(ch, out value)) { return ch; } } return default(char); } 

This might help
Start iterating through the string,

Check if it matches any other, If there's a match, it's not unique, so move to the next item and again check if it matches any other.

Do this till there is no match for the current item. If there's no other value which is equal to the current item's value, it's unique, then stop iterating and print.

 string s = "aaabbbcddeee"; bool b_duplicate=false; for (int i=0;i<s.Length;i++) { b_duplicate = false; for (int j = 0; j < s.Length; j++) { if ((s[i] == s[j]) && (i!=j)) { b_duplicate = true; break; }; } if (!(b_duplicate)) Console.WriteLine("First unique char is:" + s[i]); }