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');
        }
  • 1
    My suggestion would be instead of keeping a count of each character, simply keep track of the characters currently in contention for not repeating. Every time your code reads a character that has already occurred it has to go through your dictionary of counts. That is a lot of wasted cycles if your string is "AAAAAAA"[... * 10e99]"AAAAB" because there's no way for the compiler to optimize it away or anything. You will simply be incrementing a value for no reason for a very long time. The other suggestions are good but I don't see them as being nearly as important. – Darren Ringer Jul 1 '16 at 0:03
  • 2
    @DarrenRinger: I ran a few quick tests, and your approach is definitely the fastest so far. My suggestion takes about 25% less time, WernerCD's 50%, T3chb0t's 60% and yours 70%. Good stuff. :) – Pieter Witvoet Jul 1 '16 at 11:39
  • Dictionaries? Two loops? This seems a little over-engineered. I don't know about the performance, but here's an alternative take: dotnetfiddle.net/MM836L – Corey Ogburn Jul 1 '16 at 22:51
  • @PieterWitvoet challange accepted ;-P could you post the source code of your tests? How long were the strings, how did you generate them etc? – t3chb0t Jul 2 '16 at 9:01
  • 1
    @t3chb0t: I don't have time right now, but when I get back I'll post results and code (including the more recent answers). – Pieter Witvoet Jul 2 '16 at 10:25
up vote 17 down vote accepted

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();
}
  • 1
    By using First instead of FirstOrDefault, your Linq approach can't handle inputs with no non-repeating characters. Other than that, good points. :) – Pieter Witvoet Jun 30 '16 at 20:09
  • 2
    @somnia06 if they didn't tell me otherwise I'd use everything that helps me to solve a particular problem. What's not forbidden is allowed ;-) – t3chb0t Jun 30 '16 at 20:27
  • 1
    @WernerCD: no, it only goes over the input string once, in GroupBy. – Pieter Witvoet Jul 1 '16 at 7:50
  • 2
    Why AsQueryable??? That makes no sense at all – CodesInChaos Jul 1 '16 at 10:35
  • 1
    @Evorlor the reason why I chose a string over a char is because with a char it wouldn't be possible to use the StringComparer.OrdinalIgnoreCase but sure, as far as saving space is concerned a char would be preferable – t3chb0t Jul 1 '16 at 13:46

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', 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 one 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 the purpose of the test across. Rather than testChar, perhaps firstRepeatedCharacter would have been a more expressive variable name.

  • This is very informative. So for testing, it is okay to have a lot as long as i'm testing only one thing? I was worried that having too much test would look like clutter as well. for example for white spaces, I included them all in in unit test. – somnia06 Jun 30 '16 at 20:15
  • @somnia06 It is better to have more tests that clearly express what it is they're testing than to have fewer tests where the purpose isn't clear. If you use Nunit instead of the microsoft test framework, it supports parameterised tests through the TestCase attribute which makes it much easier to test the same test logic with different inputs. The tests on this question should give you a feel for how they work: codereview.stackexchange.com/q/128361/4203 – forsvarir Jul 1 '16 at 12:46

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.

  • "Find the first non-repeating character in a string: (“DEFD” --> E)" This was the question itself, no more no less. I asked questions about spacing and other requirements and they didn't respond for awhile so i just commented my assumptions and submitted it (I was worried they might think im taking too long). And for that algorithm comment, I would have to create another list then store only the non repeating ones then itereate over it not including the repeating ones. It make a lot of sense but wouldn't that be both o(n) either way? Thanks – somnia06 Jun 30 '16 at 20:22
  • 1
    Big-O notation tells you how well a solution scales as it's given increasingly large inputs. Constant factors are left out because they don't affect that scaling. An algorithm that performs 5 operations per input element and an algorithm that performs 1 per element are both O(n), but the latter is obviously faster. Sometimes an algorithm that is faster overall performs significantly worse for certain inputs, while another algorithm is slower overall but more stable across all inputs. Again, I wouldn't implement this initially, but I'd mention the possibility to the interviewer. – Pieter Witvoet Jul 1 '16 at 7:02

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.

  • That first IndexOf call can be removed by using a for loop. Either way, this has O(n^2) worst-case time complexity. For monotone inputs it appears to be faster than a character-counting approach (O(n), with minimal overhead), but the more distinct characters an input has the more it tends towards O(n^2). – Pieter Witvoet Jul 1 '16 at 11:00
  • Of course it has O(n^2), but as long as the question does not mention any constraints (input length, runtime, memory,...) this is about the best solution. - For bonus points, you should point out the complexity in a comment or other documentation. – JimmyB Jul 1 '16 at 11:16
  • "IndexOf call can be removed" - Not without some serious extensions to the code. Think about "AAA": For the last A, its index and last index of A are identical. – JimmyB Jul 1 '16 at 11:17
  • You're right, without keeping track of the first occurrence of a character you'll have to search for it again. – Pieter Witvoet Jul 1 '16 at 11:20
  • 1
    Any solution that has n^2 when a solution exists that is n... There is a spot for clarity and included tools, but... just me, but that is horrible. Any question like this with a decent interviewer would care about O... Every online test I practice with tests for efficiency. – WernerCD Jul 1 '16 at 13:00

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];
}
  • Turning repeatingChars into a HashSet<char> should make this O(n). – Pieter Witvoet Jul 2 '16 at 10:27

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 ' ';
    }
  • Actually, I did mention this in my answer: I suggested keeping a list of characters in order of first occurrence. By adding characters to it only when they're first encountered you end up with a list of distinct characters that's already sorted. – Pieter Witvoet Jul 1 '16 at 7:27
  • 1
    Note that Count() forces removeDuplicates to be evaluated, so together with OrderBy it's evaluated twice. Better to use Any() instead. As for adding short-circuits, more code means higher maintenance costs (it takes longer to understand the code, there's more 'room' for bugs, etc.), so personally I would only do that if it's actually necessary. – Pieter Witvoet Jul 1 '16 at 7:39
  • 2
    @PieterWitvoet You did mention it, but no one (as of that point) had explained in more detail the actual efficiency of the algorithm - and in my limited experience with these kinds of tests: efficiency is a major concern. N^2 vs 2N vs N+M vs Log(N) etc... Most everything I saw centered around the same 2N algorithm. No one else had shown a good example of a reworked algorithm. – WernerCD Jul 1 '16 at 13:09
  • Good point. Interestingly, t3chb0t's answer is also N+M, but that may not have been intentional - he didn't mention it. – Pieter Witvoet Jul 1 '16 at 13:33
  • 1
    I'm sorry we've been talking past each other in the previous comments. – JimmyB Jul 1 '16 at 15:04

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);
}
  • 2
    Thank you for improving your answer. Next time, however, you need only flag the answer for undeletion instead of posting a new one. – Jamal Feb 10 '17 at 16:56

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.