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

Question

I recently had an interview and got to phase 2 which is a coding assessment. One of the questions was:

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

I didn't pass the coding assessment and was wondering if the community can help me improve.

Solution:

     /// <summary>
    /// Assuming that letter case doesn't matter, I will convert letters to upper case.
    /// I will return ' ' if the non repeating character does not exist.
    /// 
    /// </summary>
    /// <param name="givenString">A string</param>
    /// <returns>The first non repeating character or ' '</returns>
    public static char FindFirstNonRepeatingCharacter(string givenString)
    {
        char nonRepeatingCharacter = ' ';
        Dictionary<char, int> charCounter = new Dictionary<char, int>();
        char[] charArray = givenString.ToUpper().ToCharArray();

        for (int i = 0; i < charArray.Length; i++)
        {
            char currentChar = charArray[i];

            if (charCounter.ContainsKey(currentChar)) {
                charCounter[currentChar]++;
            } else
            {
                charCounter.Add(currentChar, 1);
            }
        }

        for (int i = 0; i < charArray.Length; i++)
        {
            char currentChar = charArray[i];

            if (charCounter[currentChar] == 1)
            {
                nonRepeatingCharacter = currentChar;
                break;
            }
        }

        return nonRepeatingCharacter;
    }

Test:

        [TestMethod()]
        public void FindFirstNonRepeatingTestCharacterAllUpperCase()
        {
            string testString = "DEFD";

            char testChar = BlueWolfSolutions.FindFirstNonRepeatingCharacter(testString);

            Assert.IsFalse(testChar == 'D' && testChar == 'F');
            Assert.AreEqual('E', testChar);
        }

        /// <summary>
        /// Testing lower case entries.
        /// </summary>
        [TestMethod()]
        public void FindFirstNonRepeatingCharacterTestAllLowerCase()
        {
            string testString = "dfed";

            char testChar = BlueWolfSolutions.FindFirstNonRepeatingCharacter(testString);

            Assert.IsFalse(testChar == 'D' && testChar == 'E');
            Assert.AreEqual('F', testChar);
        }

        /// <summary>
        /// Testing mixed case entries.
        /// </summary>
        [TestMethod()]
        public void FindFirstNonRepeatingCharacterTestMixedCasing()
        {
            string testString = "EeFd";

            char testChar = BlueWolfSolutions.FindFirstNonRepeatingCharacter(testString);

            Assert.IsFalse(testChar == 'E' && testChar == 'D');
            Assert.AreEqual('F', testChar);
        }

        /// <summary>
        /// Testing numeric entries.
        /// </summary>
        [TestMethod()]
        public void FindFirstNonRepeatingCharacterTestNumeric()
        {
            string testString = "11233455";

            char testChar = BlueWolfSolutions.FindFirstNonRepeatingCharacter(testString);

            Assert.IsFalse(testChar == '1' && testChar == '3' && testChar == '4' && testChar == '5');
            Assert.AreEqual('2', testChar);
        }

        /// <summary>
        /// Testing entries with white space.
        /// </summary>
        [TestMethod()]
        public void FindFirstNonRepeatingTestWhiteSpace()
        {
            string testStringOne = " ";
            string testStringTwo = "";
            string testStringThree = "D EF D";

            char testCharOne = BlueWolfSolutions.FindFirstNonRepeatingCharacter(testStringOne);
            char testCharTwo = BlueWolfSolutions.FindFirstNonRepeatingCharacter(testStringTwo);
            char testCharThree = BlueWolfSolutions.FindFirstNonRepeatingCharacter(testStringThree);

            Assert.IsFalse(testCharThree == 'D' && testCharThree == 'F');
            Assert.IsTrue(testCharOne == ' ' && testCharTwo == ' ' && testCharThree == 'E');
        }

Answer 1

It's easier to do it with LINQ which is in this case virtually a one-liner.

var text = "DEFD";

var result = 
    text
    .AsQueryable() // this isn't necessary as noted by @CodesInChaos
    .GroupBy(c => c.ToString(), c => c, StringComparer.OrdinalIgnoreCase)
    .Where(g => g.Count() == 1)
    .Select(g => g.Key)
    .First(); // this should be FirstOrDefault as noted by @PieterWitvoet

---

As far as your code is concerned here are a few improvements:

There is no need to convert the string to lower or upper case. Instead you can use the StringComparer.OrdinalIgnoreCase. You can also use this to create a dictionary that is non-case-sensitive:

var dic = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase);

You don't have to turn a string into an array, it is an array already so you can simply iterate with a foreach over it.

Now that we know this we can shorten it too (if we are still not going to use linq to help us):

public static string FindFirstNonRepeatingCharacter(string givenString)
{
    var charCounter = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase);

    foreach (var ch in givenString)
    {
        charCounter[ch.ToString()] = 
            charCounter.ContainsKey(ch.ToString()) 
            ? charCounter[ch.ToString()] + 1 
            : 1;
    }

    foreach (var ch in givenString)
    {
        if (charCounter[ch.ToString()] == 1)
        {
            return ch.ToString();
        }
    }

    return null;
}

---

EDIT: Performance Tests

I've tested some of the suggestet solutions and here are the results:

Original (ToUpper)            Ü 00:00:00.0962950   100,00 % 
Original (StringComparer)     ü 00:00:00.4488175   466,00 % 
GroupBy (string)              ü 00:00:00.1212308   126,00 % 
GroupBy (char)                ü 00:00:00.0362518    38,00 % 
Indexed                       ü 00:00:00.1571029   163,00 % 
Custom equality char comparer ü 00:00:00.3152172   327,00 %
Not counting chars            Ü 00:00:00.0861682    90,00 % 

---

Source code:

void Main()
{
    // creating some random test string with 1.000.000 + 1 charachters

    var textBuilder = new StringBuilder();

    var length = 1000000;
    var rnd = new Random((int)DateTime.Now.Ticks);

    for (var i = 0; i < length; i++)
    {
        if (rnd.Next(1, 3) == 1)
            textBuilder.Append((char)rnd.Next(65, 91));
        else

            textBuilder.Append((char)rnd.Next(97, 123));
    }
    textBuilder.Append("ü");

    var text = textBuilder.ToString();

    // test functions and descriptions
    var funcs = new Dictionary<string, Func<string, string>>
    {
        ["Original (ToUpper)"] = FindFirstNonRepeatingCharacter0,
        ["Original (StringComparer)"] = FindFirstNonRepeatingCharacter1,
        ["GroupBy (string) "] = FindFirstNonRepeatingCharacter21,
        ["GroupBy (char) "] = FindFirstNonRepeatingCharacter22,
        ["Indexed"] = FindFirstNonRepeatingCharacter3,
        ["Custom equality char comparer"] = FindFirstNonRepeatingCharacter4,
        ["Not counting chars"] = FindFirstNonRepeatingCharacter5,
    };

    var results = new List<dynamic>();

    // running tests
    foreach (var func in funcs)
    {
        var sw = Stopwatch.StartNew();
        var ch = func.Value(text);
        sw.Stop();

        // gathering results
        results.Add(new
        {
            Func = func.Key,
            Result = ch,
            Elapsed = sw.Elapsed,
            // calculating performance in relation to OP's function
            Difference = string.Format("{0,10:P2}", results.Count == 0 ? 1 : Math.Round(sw.Elapsed.TotalMilliseconds / results[0].Elapsed.TotalMilliseconds, 2) * 1)
        });
    }

    results.Dump();
}

And the tested methods:

// by @somnia06 (OP)
public static string FindFirstNonRepeatingCharacter0(string givenString)
{
    char nonRepeatingCharacter = ' ';
    Dictionary<char, int> charCounter = new Dictionary<char, int>();
    char[] charArray = givenString.ToUpper().ToCharArray();

    for (int i = 0; i < charArray.Length; i++)
    {
        char currentChar = charArray[i];

        if (charCounter.ContainsKey(currentChar))
        {
            charCounter[currentChar]++;
        }
        else
        {
            charCounter.Add(currentChar, 1);
        }
    }

    for (int i = 0; i < charArray.Length; i++)
    {
        char currentChar = charArray[i];

        if (charCounter[currentChar] == 1)
        {
            nonRepeatingCharacter = currentChar;
            break;
        }
    }

    return nonRepeatingCharacter.ToString();
}

// by @somnia06 (OP) + modified by @t3chb0t
public static string FindFirstNonRepeatingCharacter1(string givenString)
{
    var charCounter = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase);

    foreach (var ch in givenString)
    {
        charCounter[ch.ToString()] =
            charCounter.ContainsKey(ch.ToString())
            ? charCounter[ch.ToString()] + 1
            : 1;
    }

    foreach (var ch in givenString)
    {
        if (charCounter[ch.ToString()] == 1)
        {
            return ch.ToString();
        }
    }

    return null;
}

// by @t3chb0t
public static string FindFirstNonRepeatingCharacter21(string givenString)
{
    return
        givenString
        .GroupBy(c => c.ToString(), c => c, StringComparer.OrdinalIgnoreCase)
        .Where(g => g.Count() == 1)
        .Select(g => g.Key)
        .FirstOrDefault();
}

// by @t3chb0t
public static string FindFirstNonRepeatingCharacter22(string givenString)
{
    return
        givenString     
        .GroupBy(c => c, c => c)
        .Where(g => g.Count() == 1)
        .Select(g => g.Key.ToString())
        .FirstOrDefault();
}

// by @somnia06 (OP) + modified by @t3chb0t
public static string FindFirstNonRepeatingCharacter3(string givenString)
{
    var charIndex = new Dictionary<string, List<int>>(StringComparer.OrdinalIgnoreCase);

    foreach (var x in givenString.Select((c, i) => new { c = c.ToString(), i }))
    {
        var indicies = (List<int>)null;
        if (charIndex.TryGetValue(x.c, out indicies))
        {
            indicies.Add(x.i);
        }
        else
        {
            charIndex[x.c] = new List<int>(new[] { x.i });
        }
    }

    var firstSingleCharIndex =
        charIndex
        .Where(i => i.Value.Count == 1).ToList();
    if (!firstSingleCharIndex.Any()) return "";

    return givenString[firstSingleCharIndex.Min(i => i.Value.FirstOrDefault())].ToString();
}

// by @somnia06 (OP) + modified by @t3chb0t
public static string FindFirstNonRepeatingCharacter4(string givenString)
{
    var charCounter = new Dictionary<char, int>(new UpperCaseInvariantCharComparer());

    for (int i = 0; i < givenString.Length; i++)
    {
        var ch = givenString[i];
        if (charCounter.ContainsKey(ch)) charCounter[ch]++;
        else charCounter[ch] = 1;
    }

    for (int i = 0; i < givenString.Length; i++)
    {
        var ch = givenString[i];
        if (charCounter[ch] == 1)
        {
            return ch.ToString();
        }
    }


    return null;
}

class UpperCaseInvariantCharComparer : IEqualityComparer<char>
{
    public bool Equals(char x, char y) => Char.ToUpperInvariant(x) == Char.ToUpperInvariant(y);

    public int GetHashCode(char x) => Char.ToUpperInvariant(x).GetHashCode();
}

// by @AhmadIbrahim
public static string FindFirstNonRepeatingCharacter5(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].ToString();
}

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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];
}

Answer 6

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 ' ';
    }

Answer 7

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);
}

Answer 8

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]);
        }