String Algorithm - Validating If String Has Unique Characters

Problem Statement 

 

Write a program to validate if the given string contains unique characters or not; which means that the given string should not contain any characters twice or multiple times. You need to consider that the comparison is case non-sensitive and the whitespace is significant.

 

Example 1

 

Input - s1 = "hemant”

Output - No Duplicate characters found in the string

Explanation - s1 does contain each character one time.

 

Example 2

 

Input - s1 = "hemantH"

Output - Duplicate characters found in the string

Explanation - s1 contains character h two times irrespective of case sensitive.

 

Example 3

 

Input - s1 = "hemant H"

Output - Duplicate characters found in the string

Explanation - s1 contains character h two times irrespective of case sensitive and white space is significant.

 

Solution

 

Look at the steps described below for the algorithm.

 

Step 1 - First, validate the length of the given string

 

As per the ASCII standard character set, there are 128 characters for electronic communication. If the length of the given string is more than 128 characters, then print the result “Duplicate characters found in the string” and exit the program; else, continue with step 2.

 

Please note that more than 128 characters in the given string indicate that the string contains one or more characters twice or multiple times

 

Step 2 - Convert the given string into an array of type character

 

Declare an array of integer type with the size 128 that maps the ASCII value because as per the ASCII standard character set, there are 128 characters for electronic communication. Iterate through the first array and for the index matching with the character ASCII value, increment the value in the integer array by 1 if the value is 0. Otherwise, print the result “Duplicate characters found in the string” and exit the program.

 

Complete code of the algorithm

Here, I have given the complete program for finding if a given string contains duplicate characters. The code is well-commented to make you understand what each line means. 

namespace HasUniqueCharacters
{
    /// Write a program to validate if the given string contains unique characters which means that the give string does not contain any character twice or multiple times
    /// You need to consider that comparison is case non-sensitive and whitespace is significant
    /// ============================================================
    /// For example 1:
    /// Input: s1 = "hemant"  Output: No Duplicate characters found in string
    /// Explanation: s1 does contain each character one time.
    /// ============================================================
    /// For example 2: "hemantH";
    /// Input: s1 = "hemantH" Output: Duplicate characters found in string
    /// Explanation: s1 contains character h two times irrespective of case sensitive.
    ///
    /// For example 3: "hemant H";
    /// Input: s1 = "hemantH" Output: Duplicate characters found in string
    /// Explanation: s1 contains character h two times irrespective of case sensitive and white space is significant.
    class Program
    {
        static void Main(string[] args)
        {
            Console.Write("Please enter string to be processed: ");
            var inputString = Console.ReadLine();

            if (!string.IsNullOrWhiteSpace(inputString))
            {
                //as per the ASCII standard character set there are 128 characters for electronic communication
                //so the length of the given string is more than 128 means string contain character multiple times
                if (inputString.Length > 128)
                {
                    Console.WriteLine("Duplicate characters found in string");
                }

                bool hasUniqueCharacters = HasUniqueCharacters(inputString);
                Console.WriteLine(hasUniqueCharacters ? "No Duplicate characters found in string" : "Duplicate characters found in string");
            }

            Console.ReadLine();
        }

        private static bool HasUniqueCharacters(string inputString)
        {
            string stringToBeProcessed = inputString.Replace(" ", "").ToLower();
            //Convert string into an array f characters
            char[] chars = stringToBeProcessed.ToCharArray();
            //declare an array of integer type with size 128 because as per the ASCII standard character set
            //there are 128 characters for electronic communication.
            int[] characterSetMappingTable = new int[128];

            //Iterate through an array and for the index matching with the character ASCII value,
            //increment the value in the integer array by 1 if the value is 0 otherwise return false if the value is already 1
            foreach (char c in chars)
            {
                var characterIndex = (int)c;
                if (characterSetMappingTable[characterIndex] >= 1)
                    return false;
                characterSetMappingTable[characterIndex]++;
            }

            return true;
        }
    }
}

Time Complexity

 

O(n) - Let me explain how this is calculated. The array iteration takes O(n) time to iterate through n characters where n is the length of the string.

 

Note
Please feel free to propose or suggest a solution you think can be followed to make it better and more optimized.