CODEWITHSUNDEEP
c#algorithm
mynameisneo
mynameisneo

Reputation: 483

Determine if string has all unique characters

I'm working through an algorithm problem set which poses the following question:

"Determine if a string has all unique characters. Assume you can only use arrays".

I have a working solution, but I would like to see if there is anything better optimized in terms of time complexity. I do not want to use LINQ. Appreciate any help you can provide!

static void Main(string[] args)
{
    FindDupes("crocodile");
}

static string FindDupes(string text)
{
    if (text.Length == 0 || text.Length > 256)
    {
        Console.WriteLine("String is either empty or too long");
    }

    char[] str = new char[text.Length];
    char[] output = new char[text.Length];

    int strLength = 0;
    int outputLength = 0;

    foreach (char value in text)
    {
        bool dupe = false;
        for (int i = 0; i < strLength; i++)
        {
            if (value == str[i])
            {
                dupe = true;
                break;
            }
        }
        if (!dupe)
        {
            str[strLength] = value;
            strLength++;

            output[outputLength] = value;
            outputLength++;
        }
    }
    return new string(output, 0, outputLength);
}

Upvotes: 2

Views: 11169

Answers (8)

Pakaj Jadhav
Pakaj Jadhav

Reputation: 16

You can try this

public static bool uniqueCharactersUsingStorage(string str)
    {
        int length = str.Length;
        string[] arrayOfCharacters = new string[length];
        for(int i = 0; i < str.Length; i++)
        {
            string val = str[i].ToString();
            if (arrayOfCharacters.Contains(val))
            {
                return false;
            }
            arrayOfCharacters[i] = val;
        }
        return true;
    }

Upvotes: 0

user11523568
user11523568

Reputation:

Remove Duplicates in entire Unicode Range

Not all characters can be represented by a single C# char. If you need to take into account combining characters and extended unicode characters, you need to:

  • parse the characters using StringInfo
  • normalize the characters
  • find duplicates amongst the normalized strings

Code to remove duplicate characters:

We keep track of the entropy, storing the normalized characters (each character is a string, because many characters require more than 1 C# char). In case a character (normalized) is not yet stored in the entropy, we append the character (in specified form) to the output.

public static class StringExtension
{
    public static string RemoveDuplicateChars(this string text)
    {
        var output = new StringBuilder();
        var entropy = new HashSet<string>();
        var iterator = StringInfo.GetTextElementEnumerator(text);

        while (iterator.MoveNext())
        {
            var character = iterator.GetTextElement();
            if (entropy.Add(character.Normalize()))
            {
                output.Append(character);
            }
        }

        return output.ToString();
    }
}

Unit Test:

Let's test a string that contains variations on the letter A, including the Angstrom sign Å. The Angstrom sign has unicode codepoint u212B, but can also be constructed as the letter A with the diacritic u030A. Both represent the same character.

 // ÅÅAaA 
 var input = "\u212BA\u030AAaA";

 // ÅAa
 var output = input.RemoveDuplicateChars();

Further extensions could allow for a selector function that determines how to normalize characters. For instance the selector (x) => x.ToUpperInvariant().Normalize() would allow for case-insensitive duplicate removal.

Upvotes: 0

Bassam Bsata
Bassam Bsata

Reputation: 1135

public static bool CheckUnique(string str)
{
    int accumulator = 0;
    foreach (int asciiCode in str)
    {
        int shiftedBit = 1 << (asciiCode - ' ');
        if ((accumulator & shiftedBit) > 0)
            return false;
        accumulator |= shiftedBit;
    }
    return true;
}

Upvotes: -1

Praveen Singh
Praveen Singh

Reputation: 29

If the string has only lower case letters (a-z) or only upper case letters (A-Z) you can use a very optimized O(1) solution.Also O(1) space.

c++ code :

bool checkUnique(string s){
    if(s.size() >26)
        return false;
    int unique=0;
    for (int i = 0; i < s.size(); ++i) {
        int j= s[i]-'a';
        if(unique & (1<<j)>0)
            return false;
       unique=unique|(1<<j);
   }
   return true;
}

Upvotes: 0

Ian Mercer
Ian Mercer

Reputation: 39277

If time complexity is all you care about you could map the characters to int values, then have an array of bool values which remember if you've seen a particular character value previously.

Something like ... [not tested]

bool[] array = new bool[256]; // or larger for Unicode

foreach (char value in text)
  if (array[(int)value])
    return false;
  else
    array[(int)value] = true;

return true;

Upvotes: 10

AkxumiteEmpire
AkxumiteEmpire

Reputation: 53

The following code works:

 static void Main(string[] args)
    {
        isUniqueChart("text");
        Console.ReadKey();

    }

    static Boolean isUniqueChart(string text)
    {
        if (text.Length == 0 || text.Length > 256)
        {
            Console.WriteLine(" The text is empty or too larg");
            return false;
        }
        Boolean[] char_set = new Boolean[256];
        for (int i = 0; i < text.Length; i++)
        {
            int val = text[i];//already found this char in the string
            if (char_set[val])
            {
                Console.WriteLine(" The text is not unique");
                return false;
            }
            char_set[val] = true;
        }
        Console.WriteLine(" The text is unique");
        return true;
    }

Upvotes: 0

Victor Mukherjee
Victor Mukherjee

Reputation: 11025

public boolean ifUnique(String toCheck){
    String str="";
    for(int i=0;i<toCheck.length();i++)
    {
         if(str.contains(""+toCheck.charAt(i)))
             return false;
         str+=toCheck.charAt(i);
    }
    return true;
}

EDIT:

You may also consider to omit the boundary case where toCheck is an empty string.

Upvotes: 1

John Woo
John Woo

Reputation: 263683

try this,

    string RemoveDuplicateChars(string key)
    {
        string table = string.Empty;
        string result = string.Empty;
        foreach (char value in key)
        {
            if (table.IndexOf(value) == -1)
            {
                table += value;
                result += value;
            }
        }
        return result;
    }

usage

Console.WriteLine(RemoveDuplicateChars("hello"));
Console.WriteLine(RemoveDuplicateChars("helo"));
Console.WriteLine(RemoveDuplicateChars("Crocodile"));

output

helo
helo
Crocdile

Upvotes: 3

Related Questions