String Contains Unique Set of Characters – Write an static method and extension method as well

Below code explains to determine if a string has all unique characters.

Assumption : String is ASCII character set and not Unicode. We’ll assume for simplicity that the character set is ASCII. If not, we would need to increase the storage size, but the rest of the logic would be the same.

Approach:
There are only 256 unique ASCII characters so any string length greater than 256 bound to have duplicate set of ASCII characters. Create an array of boolean values, where the flag at index i indicates, whether character i in the alphabet is contained in the string. If you run across this character a second time, you can immediately return false.

Below is the code snippet, code snippet also has string extension method as well.

    class Program
    {
        /// <summary>
        /// Strings the contains unique characters.
        /// Assmuption : String is ASCII character set and not unicode. 
        /// The time complexity for this code is 0(n), where n is the length of the string.The space
        /// complexity is 0(1).
        /// 
        /// </summary>
        /// <param name="input">The input.</param>
        /// <returns></returns>
        public static bool StringContainsUniqueCharacters(string input)
        {
            //There are only 256 unique ASCII characters so any string length greater than 256 
            //bound to have duplicate set of characters.
            if (input.Length > 256) return false;

            // Create an array of boolean values, where the flag at index i indicates
            // whether character i in the alphabet is contained in the string. If you run across this
            // character a second time, you can immediately return false.
            bool[] charArr = new bool[256];

            //Iterate through all characters.
            foreach (char c in input)
            {
                if (charArr[(int)c])
                {
                    return false;
                }
                else
                {
                    charArr[(int)c] = true;
                }
            }
            return true;
        }

        static void Main(string[] args)
        {
            string str = "aamol";
            Console.WriteLine("String "+ str + " contains unique characters "  + StringContainsUniqueCharacters(str));
            str = "amol";
            Console.WriteLine("String " + str + " contains unique characters " + StringContainsUniqueCharacters(str));
            Console.ReadLine();
            str = "aamol";
            Console.WriteLine("String " + str + " contains unique characters " + str.ContainsUniqueCharacters());
            str = "amol";
            Console.WriteLine("String " + str + " contains unique characters " + str.ContainsUniqueCharacters());
            Console.ReadLine();
        }
    }
    public static class StringUtlity
    {
        /// <summary>
        /// Strings the contains unique characters Extension Method.
        /// Assmuption : String is ASCII character set and not unicode. 
        /// The time complexity for this code is 0(n), where n is the length of the string.The space
        /// complexity is 0(1).
        /// 
        /// </summary>
        /// <param name="input">The input.</param>
        /// <returns></returns>
        public static bool ContainsUniqueCharacters(this string input)
        {
            //There are only 256 unique ASCII characters so any string length greater than 256 
            //bound to have duplicate set of characters.
            if (input.Length > 256) return false;

            // Create an array of boolean values, where the flag at index i indicates
            // whether character i in the alphabet is contained in the string. If you run across this
            // character a second time, you can immediately return false.
            bool[] charArr = new bool[256];

            //Iterate through all characters.
            foreach (char c in input)
            {
                if (charArr[(int)c])
                {
                    return false;
                }
                else
                {
                    charArr[(int)c] = true;
                }
            }

            return true;
        }

    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s