Hi folks,

This doesn't look difficult right :) however can u think of different ways to find first non-repeated character in a string?

I tried 3 different ways in C#. One with O(n^2) and 2 ways with O(n). Please suggest if you can think of better ways :)

 ///Complexity: O(n^2)

public static char FirstNonRepeatedCharInString (string str)
        {
            int i, j;
            bool isRepeted = false;

            char[] chars = str.ToCharArray();

            for (i=0; i<chars.Length;i++)
            {
                isRepeted = false;
                for (j=0;j<chars.Length;j++)
                {
                    if ((i!=j) && (chars[i]==chars[j]))
                    {
                        isRepeted = true;
                        break;
                    }
                }

                if (isRepeted ==false)
                {
                    return chars[i];
                }
            }
            return ' ';
        }

 ---------------------------------------------------------------------------------------------

 ///Complexity: O(n)

public static char FirstNonRepeatedCharInString2(string str)
        {
            Dictionary<char, int> l1 = new Dictionary<char, int>();
            int temp = 0;

            foreach (char c in str.ToCharArray())
            {
                if (l1.Keys.Contains(c))
                {
                    temp = l1[c];
                    l1[c] = temp + 1;
                    continue;
                }
                l1.Add(c,1);
            }

            if (l1.Values.Contains(1))
            {
                return l1.First(x => x.Value == 1).Key;
            }
            return ' ';
        }

----------------------------------------------------------------------------------------------

///Complexity: O(256) + O(n) + O(n) = O(n)

public static char FirstNonRepeatedCharInString3(string str)
        {
            int[] chars = new int[256];
            for (int i = 0; i < chars.Length; i++)
            {
                chars[i] = 0;
            }

            for (int i = 0; i < str.Length; i++)
            {
                chars[str[i]]++;
            }

            for (int i = 0; i < str.Length; i++)
            {
                if (chars[str[i]] == 1)
                {
                    return str[i];
                }
            }
            return ' ';
        }

 

Happy Programming!!